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