Замечание о представлении произвольной формулы многочленом Жегалкина.
Замечание о представлении произвольной формулы многочленом Жегалкина. - раздел Математика, КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
Введём Следующие Обозначения: ...
Введём следующие обозначения: , . Тогда конъюнкция станет обычным умножением символов и . Действительно:
Договоримся далее в наших рассуждениях обозначать конъюнкцию точкой и опускать её в записи формул (как принято в алгебре). Например, . Такие произведения будем называть одночленами Жегалкина. Одночлены, объединённые знаком «+», называются многочленами Жегалкина.
Известно, что система операций полна, причём , поэтому всякую формулу алгебры логики можно преобразовать с помощью операций . Это значит, что любую формулу алгебры логики можно представить многочленом Жегалкина, причём единственным образом. Чтобы получить такое представление нужно выразить все логические операции, входящие в формулу, через конъюнкцию и отрицание, учитывая, что , . Далее нужно раскрыть скобки, привести подобные слагаемые, имея в виду, что для любых одночленов выполняются свойства: , , , .
Представим основные логические операции многочленами Жегалкина.
1) - есть многочлен Жегалкина (одночлен второй степени);
2)
(здесь учитывается, что 1 + 1 = 0);
3) .
Эквивалентность рассматривается аналогично.
Рассмотрим для примера следующую формулу: . Получим представление этой формулы в виде многочлена Жегалкина:
Упражнения для самостоятельной работы.
1. Даны следующие высказывания:
P = «Данное число – целое»,
Q = «Данное число – положительное»,
R = «Данное число – простое»,
S = «Данное число
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются формулы из некоторых
Алгоритм преобразования произвольной формулы в СНДФ.
1) Выразить все логические операции через конъюнкцию, дизъюнкцию и отрицание.
2) Используя дистрибутивные законы, преобразовать формулу так, чтобы все конъюнкции выполнялись раньше дизъюнк
Определения.
В математике принято одной и той же буквой обозначать различные объекты, т. е. под буквой фактически понимается переменная, принимающая значения из некоторого множества. Такие перем
Упражнения для самостоятельной работы.
1. Записать следующие высказывания в виде формул логики предикатов.
1) Всякое натуральное число, делящееся на 12, делится на 2, 4 и
Упражнения для самостоятельной работы.
1.Записать на языке логики предикатов аксиому математической индукции.
2. Записать на языке логики предикатов следующую те
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём сле
, 
. Тогда конъюнкция станет обычным умножением символов 
и 
. Действительно:
. Такие произведения будем называть одночленами Жегалкина. Одночлены, объединённые знаком «+», называются многочленами Жегалкина.
полна, причём 
, поэтому всякую формулу алгебры логики можно преобразовать с помощью операций 
. Это значит, что любую формулу алгебры логики можно представить многочленом Жегалкина, причём единственным образом. Чтобы получить такое представление нужно выразить все логические операции, входящие в формулу, через конъюнкцию и отрицание, учитывая, что 
. Далее нужно раскрыть скобки, привести подобные слагаемые, имея в виду, что для любых одночленов выполняются свойства: 
, 
, 
, 
.
- есть многочлен Жегалкина (одночлен второй степени);
.
. Получим представление этой формулы в виде многочлена Жегалкина:
= 
= 
= 
= 
.
Новости и инфо для студентов