Методические указания к самостоятельным (домашней и контрольной) работам по курсу «Математическая логика и теория алгоритмов» (стр. 2 )

9). (ВА) ((ВА) В)

10). ((АВ) А) А закон Пирса

При доказательстве эквивалентностей или равносильностей надо либо правую формулу равносильными преобразованиями свести к левой, либо левую к правой, либо обе к какой-то одной, третьей формуле. Если требуется доказать тождественную истинность формулы, то её надо равносильными преобразованиями свести к вышеизложенным тождествам. Если заданий несколько, то не более половины можно выполнить с помощью таблицы истинности. Например, докажем девятую равносильность: А(АВ)(АА)(АВ)А(АВ)А. Здесь использованы восьмая, вторая и десятая равносильности.

Логические символы и называют двойственными друг другу. Рассмотрим формулы, содержащие только эти логические символы и инверсию. Формула Адвойственна формуле А, если она получена из А одновременной заменой и на двойственные.

Система булевых функций называется полной, если любая булева функция может быть выражена через функции системы с помощью суперпозиций. Например, система из трёх функций {, , } является полной. Если система функций полная и любая из функций этой системы может быть выражена с помощью суперпозиций через функции второй системы функций, то эта вторая система функций тоже является полной. В общем случае для проверки полноты системы функций надо составлять таблицу Поста. Она нужна для проверки теоремы Поста для этой системы: Если система полная, то для каждого из функционально замкнутых классов T, T, S, L и M найдётся функция из системы, не принадлежащая этому классу. Например, для системы {, , } таблица Поста имеет вид:

Функция	T	T	S	L	M
	+	+	-	-	+
	+	+	-	-	+
	-	-	+	+	-

Эта система функций является полной, так как в каждом столбце таблицы присутствует «-». Функция принадлежит T, если во всех нулях она равна нулю, и принадлежит T, если во всех единицах она равна единице. Функция f(x, y, … ,w) самодвойственна, если f(x, y, … ,w)= f(x, y, … , w). Функция линейна, если линеен её полином Жигалкина. Для инверсии полином Жигалкина имеет вид: x+1=x, он линеен и «+» - это сложение по модулю два. Для дизъюнкции: xy=xy+x+y, он не линеен и xy – это xy, это и есть нелинейность. Монотонная функции не должна упасть на возросшем наборе переменных. Набор переменных возрос, если все переменные или увеличились, или не изменились. Система функций независима, если ни какая функция из системы не может быть выражена с помощью суперпозиций через остальные функции системы. Система {,} независима, так как T, T, L, L. Система {, , } зависима, смотри выше законы Моргана.

x	y	z	f
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

Формулу называют элементарной конъюнкцией, если она является конъюнкцией (может быть и одночленной) переменных и отрицаний переменных: xy, xyz. Формула находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией (может быть и одночленной) элементарных конъюнкций: (xy) (xyz). Формула находится в Совершенной ДНФ (СДНФ), если каждый её дизъюнктивный член содержит по одному разу в прямом или инверсном виде все переменные формулы, и все её дизъюнктивные члены попарно различны: (xyz) (xyz) (xyz). Аналогично определяются элементарная дизъюнкция, КНФ и СКНФ. Приводить формулы к их нормальным формам надо используя равносильные преобразования. Для приведения к совершенным формам можно использовать таблицы истинности формул: пусть f(x, y,z)=(xz)(yz), СДНФ получается из единиц функции, а СКНФ – из нулей. При получении СДНФ нули переменных переходят в их инверсии: (xyz)(xyz)(xyz)(xyz), здесь элементарные конъюнкции получены последовательно из наборов переменных (001), (100), (101) и (110). При получении СКНФ единицы переменных переходят в их инверсии.

Минимизация проводится в классе ДНФ методом минимизирующих карт. Функция должна быть задана её таблицей истинности или её СДНФ. Минимизирующая карта имеет 2строк, где n – число переменных функции, и на единицу меньше столбцов. Например, для n=3:

x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz

Использование карты основано на следующем: если какая то конъюнкция последнего столбца карты не входит в СДНФ функции, то все конъюнкции этой строки не входят ни в одну ДНФ функции. Возьмём функцию f(x, y,z)=(xz)(yz) с таблицей истинности, представленной выше. Далее убираем из карты строки, соответствующие конъюнкциям, не вошедшим в СДНФ функции: