Практическое применение методов математической логики

 

Всякая логическая функция «n» переменных может быть задана таблицей, в левой части которой перечислены все 2ⁿ наборов значений переменных (то есть всевозможных наборов двоичных векторов длины «n»), а в правой части приведены значения функции на этих наборах. При любом фиксированном упорядочении наборов значений переменных логическая функция «n» переменных полностью определена вектор-столбцом своих значений, то есть вектором длины 2ⁿ. Поэтому число различных логических функций «n» переменных будет . В самом деле, для одного набора значений своих переменных (строка левой части таблицы) значение функции может быть либо 1, либо 0 (две возможности). Число же возможных различных наборов аргументов функции, как уже отмечалось равно 2ⁿ, поэтому число различных логических функций будет /1/.

Заданием в данном пункте является построение таблицы истинности для следующего высказывания:

 

,

 

Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. “Истинность” или “ложность” предложения – это истинностное значение высказывания. Каждому высказыванию сопоставляется переменная, равная 1, если высказывание истинно, и равная 0, если оно ложно. Эти высказывания будут считаться простыми. Из простых высказываний с помощью логических связок могут быть построены составные высказывания. В таблице 1 приведены некоторые логические связки, используемые при задании данной функции (1).

 

Таблица 1-Логические связки

Название	Обозначение
Конъюнкция	&
Импликация	®
Сумма по модулю два	Å
Штрих Шеффера	|
Отрицание	Ø
Дизъюнкция	Ú
Стрелка Пирса	¯

 

Правильно построенные составные высказывания называются (пропозиционарными) формулами. Истинностное значение формулы определяется через истинностные значения её составляющих в соответствии с единой таблицей истинности (таблица 2).

 

Таблица 2-Истиностные значения формул высказывания

Х1	Х2	X1 &X2	X1® X2	X1 ÅX2	X1Ú X2	ØX1	X1¯ X2
0	0	0	1	0	0	1	1
0	1	0	1	1	1	1	0
1	0	0	0	1	1	0	0
1	1	1	1	0	1	0	0

 

Для того чтобы составить таблицу истинности для формулы, необходимо выполнить последовательность всех логических операций.

 

, (1)

 

После последовательного выполнения всех логических операций составляется таблица истинности для данной функции

Таблица 3- Таблица истинности функции (1)

1	2	3	4	5	6	7	8	9	10
x	y	z	&
0	0	0	0	1	1	1	0	0	0
0	0	1	0	1	1	1	0	0	0
0	1	0	0	1	0	1	0	0	1
0	1	1	0	1	0	0	1	1	0
1	0	0	0	1	1	1	0	1	0
1	0	1	1	1	1	1	0	1	0
1	1	0	0	1	0	1	0	1	0
1	1	1	1	1	0	0	1	1	0

Приведение функции к конъюнктивным и дизъюнктивным нормальным формам. Конъюнктивным (дизъюнктивным) одночленом от переменных а₁, а₂, а₃,…,а _n называется конъюнкция (дизъюнкция) этих переменных или их отрицаний. Формула, равносильная данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных произведений (конъюнктивных одночленов), называется дизъюнктивной нормальной формой (ДНФ) данной формулы. Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных произведений (дизъюнктивных одночленов), называется конъюнктивной нормальной формой (КНФ) данной формулы /2/. Справедливы следующие теоремы: любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде ДНФ по формуле:

 

V     (2)

 

Любая булева функция, тождественно не равная единице представима и притом единственным образом в виде КНФ.

 

L (3).

 

Любая булева функция представима формулой, в которую входит только конъюнкция, дизъюнкция и отрицание /2/.

Искомая ДНФ для функции (1) имеет вид:

 

 

Искомая КНФ для функции (1) будет иметь следующий вид:

 

 

В расчетах ДНФ и КНФ использована методика /2/.

Построение полинома Жегалкина.

Представление булевой функции над базисом {0,1,v,Å} называется полиномом Жегалкина.

Таким образом, всякая булева функция представима в виде:

 

   

 

где ∑ - сложение по модулю два, знак · обозначает конъюнкцию/7/.

Для функции f (x, y, z) (1) полином Жегалкина имеет вид:

 

P(x, y, z)=b₀×1Åb₁×xÅb₂×yÅb₃×zÅb₄×x×yÅb₅×x×zÅb₆y×zÅb₇x×y×z

 

Метод неопределенных коэффициентов заключается в том, что путем последовательной подстановки переменных x, y, z и соответственно значений функции при этих переменных, из таблицы 1 в данный полином (4), строится система уравнений:

 

0=b₀×1Åb₁×0Åb₂×0Åb₃×0Åb₄×0×0Åb₅×0×0Åb₆0×0Åb₇0×0×0

0=b₀×1Åb₁×0Åb₂×0Åb₃×1Åb₄×0×0Åb₅×0×1Åb₆0×1Åb₇0×0×1

1=b₀×1Åb₁×0Åb₂×1Åb₃×0Åb₄×0×1Åb₅×0×0Åb₆1×0Åb₇0×1×0

0=b₀×1Åb₁×0Åb₂×1Åb₃×1Åb₄×0×1Åb₅×0×1Åb₆1×1Åb₇0×1×1

0=b₀×1Åb₁×1Åb₂×0Åb₃×0Åb₄×1×0Åb₅×1×0Åb₆0×0Åb₇1×0×0

0=b₀×1Åb₁×1Åb₂×0Åb₃×1Åb₄×1×0Åb₅×1×1Åb₆0×1Åb₇1×0×1

0=b₀×1Åb₁×1Åb₂×1Åb₃×0Åb₄×1×1Åb₅×1×0Åb₆1×0Åb₇1×1×0

0=b₀×1Åb₁×1Åb₂×1Åb₃×1Åb₄×1×1Åb₅×1×1Åb₆1×1Åb₇1×1×1

 

По свойству суммы по модулю два находится b:

 

b₀=0, b₁=0, b₂=1, b₃=0, b₄=1, b₅=0, b₆=1, b₇=1

 

Полином Жегалкина будет иметь вид:

 

¦(x, y, z) = y Å x×y Å y×z Å x×y×z

 

Правильность построения полинома проверяется таблицей истинности:

 

Таблица 4 - Таблица истинности для полинома Жегалкина

1	2	3	4	5	6	7	8	9
x	y	z	x&y	Å	y&z	Å	x&y&z	Å
0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0
0	1	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0	0
1	0	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
1	1	0	1	0	0	0	0	0
1	1	1	1	0	1	1	1	0

 

Дифференцирование функции нескольких переменных.

Производной булевой функции ¦(xⁿ) по совокупности переменных  называется функция:

 

 

На основе данной формулы (5) находится производная по одной переменной x

 

 

Для данной функции (1) производная по формуле (6) принимает вид:

 

 

Таблица 5 - Производная ∂¦⁄∂ x для формулы(7)

1	2	3	4	5	6	7	8	9	10	11	12	13
x	y	z		&
0	0	0	1	0	1	1	1	0	1	0	0	0
0	0	1	1	1	1	1	1	0	1	0	0	0
0	1	0	1	0	1	0	1	0	1	1	1	0
0	1	1	1	1	1	0	0	1	1	1	0	1
1	0	0	0	0	1	1	1	0	0	1	0	1
1	0	1	0	0	1	1	1	0	0	1	0	1
1	1	0	0	0	1	0	1	0	0	0	0	0
1	1	1	0	0	1	0	0	1	1	1	0	1

 

Вектор значений функции (7) имеет вид:

 

 

Производная по двум переменным находится также по формуле (5):

 

 

Для данной функции (1) производная принимает вид:

 

 

 

Таблица 6 - Производная ∂²¦⁄∂(x; y) для формулы(9)

1	2	3	4	5	6	7	8	9	10	11	12
x			&
0	1	1	0	1	1	1	0	1	0	0	0
0	1	0	0	1	1	1	0	1	0	0	0
0	0	1	0	1	0	1	0	1	1	1	0
0	0	0	0	1	0	0	1	1	1	0	1
1	1	1	1	1	1	1	0	0	1	0	1
1	1	0	0	1	1	1	0	0	1	0	1
1	0	1	1	1	0	1	0	0	0	0	0
1	0	0	0	1	0	0	1	1	1	0	1

 

Вектор значений функции (6) имеет вид:

 

Применение теории графов