1.6. Подстановка и замена
Если в формулу
входит
переменная х, то это можно обозначить
как
.
Если в формулу входит подформула
,
то обозначим это как
.
Вместо подформулы или переменной можно подставить другую формулу или переменную. В результате получится новая правильно построенная формула.
Если подстановка производится вместо всех вхождений заменяемой переменной или подформулы, то результат обозначим:
{
,
т. е. все вхождения переменной х заменяем
на подформулу
.
Если подстановка производится вместо некоторых вхождений, то результат обозначим
,
т. е. первое вхождение
заменяем
на
.
Примеры.
Замена всех вхождений переменной х
Замена всех вхождений подформулы
Замена первого вхождения переменной х
Замена первого вхождения подформулы
Правило подстановки. Если в равносильных формулах вместо всех вхождений некоторой переменной xподставить одну и ту же формулу, то получатся равносильные формулы.
Правило замены. Если в формуле заменить некоторую подформулу на равносильную, то получится равносильная формула.
1.7. Формы представления высказываний
Нормальная форма – это синтаксически однозначный способ записи формулы, реализующей данную функцию.
Любую булеву формулу можно привести к равносильной ей формуле простого стандартного вида, которой будет являться дизъюнкция элементов, каждый из которых представляет собой конъюнкцию отдельных различных логических переменных либо со знаком отрицания, либо без него.
Пример.
Такая форма называется дизъюнктивной нормальной формой (ДНФ). Отдельный элемент ДНФ называется элементарной конъюнкцией или конституентой единицы.
Аналогично любую формулу можно привести к равносильной ей формуле, которая будет являться конъюнкцией элементов, каждый из которых будет представлять собой дизъюнкцию логических переменных со знаком отрицания или без него. Такая форма называется конъюнктивной нормальной формой (КНФ).
Пример.
Отдельный элемент КНФ называется элементарной дизъюнкцией или конституентой нуля.
СДНФ (совершенная ДНФ) – это такая ДНФ, в которой каждая элементарная конъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу, элементарные конъюнкции не повторяются.
Пример.
СКНФ (совершенная КНФ) – это такая КНФ, в которой каждая элементарная дизъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу, элементарные дизъюнкции не повторяются.
Пример.
Каждая формула имеет одну единственную СДНФ и одну единственную СКНФ. Тавтология не имеет СКНФ, а противоречие – СДНФ.
Как мы знаем, каждая формула логики высказываний представляет некоторую булеву функцию. Возникает обратный вопрос: можно ли всякую булеву функцию представить некоторой формулой логики высказываний? Можно указать алгоритм, который позволяет по таблице истинности произвольной булевой функции от любого числа переменных построить некоторую формулу логики высказываний в СДНФ.
Пример.
Рассмотрим частный случай. Пусть f(x,y,z)=1 только в одном единственном случае.
|
x |
y |
z |
f(x,y,z) |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
Тогда этой формуле будет соответствовать
функция
.
Если рассматривать произвольную функцию, то необходимо выделить все наборы переменных, для которых функция принимает значение 1 и каждому набору поставить в соответствие конъюнкцию переменных и их отрицаний. Рассматриваемая функция будет представлена дизъюнкцией этих конъюнкций.
Таким образом, установлена процедура, которая позволяет для всякой булевой функции записать соответствующую ей формулу.
Пример.
|
x |
y |
z |
f(x,y,z) |
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
Выводы:
Каждая формула логики высказываний представляет собой некоторую булеву функцию и наоборот.
Различные формулы могут представить одну и ту же функцию (равносильные формулы) .
Существует много дизъюнктивных форм равносильных между собой.