Функции алгебры логики. Совершенные нормальные формы

Определение 1. Функцией алгебры логики п перемен­ных называется любая функция n переменных F(x₁,x₂,...,x_n), аргументы которой принимают два зна­чения 1 и 0, и сама функция принимает одно из двух значений: 1 или 0.

Всякая формула алгебры логики есть функция ал­гебры логики. Тождественно истинная и тождественно ложная формулы есть постоянные функции.

Можно показать, что всякую функцию алгебры ло­гики можно представить в виде формулы алгебры логи­ки, и это представление таково:

F(x₁,x₂,...,x_n) = F(1,1,...,1)&x₁&x₂&...&x_n

F(l, 1,..., 0) & х₁ х₂&...& х_n-1 & . (*)

Формулу (*) можно преобразовать к формуле, ко­торая содержит только элементарные переменные выс­казывания и обладает следующими свойствами совер­шенства (или свойствами (С)):

1) каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x₁,x₂,...,x_n);

2) все логические слагаемые формулы различны;

3) ни одно логическое слагаемое формулы не содер­жит одновременно переменную и ее отрицание;

4) ни одно логическое слагаемое формулы не содер­жит одну и ту же переменную дважды.

С помощью таблицы истинности, определяющей фун­кцию F(x₁,x₂,…,x_n), легко получить соответствующую формулу алгебры логики, обладающую свойствами (С). Действительно, для каждого набора значений перемен­ных, на котором функция F(x₁,x₂,...,x_n) принимает зна­чение 1, запишем конъюнкцию элементарных перемен­ных высказываний, взяв за член конъюнкции x_k, если

значение x_k на указанном наборе значений переменных есть 1, и отрицание х_k, если значение х_k есть 0. Дизъюн­кция всех полученных таким образом конъюнкций и будет искомой формулой.

Определение 2. Элементарной конъюнкцией п пере­менных называется конъюнкция переменных или их отрицаний.

Определение 3. Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей форму­ла, представляющая собой дизъюнкцию элементарных

конъюнкций.

Определение 4. Совершенной дизъюнктивной нор­мальной формой (СДНФ) формулы А называется ДНФ А, обладающая свойствами (С).

СДНФ А можно получить двумя способами: а) с по­мощью таблицы истинности (см. выше); б) с помощью равносильных преобразований.

Правило получения СДНФ из формулы А с помо­щью равносильных преобразований.

1. Для формулы А получаем любую ДНФ.

2. Из ДНФ А путем равносильных преобразований получаем СДНФ, последовательно добиваясь выполнения четырех свойств СДНФ:

1) Пусть В есть слагаемое ДНФ, не содержащее х_i. Тогда надо заменить слагаемое В в ДНФ А на слагаемое .

2) Если в ДНФ А встретится два одинаковых слага­емых B В, то лишнее нужно отбросить, так как .

3) Если в некоторое слагаемое В в ДНФ А перемен­ная x_i входит дважды, то лишнюю переменную надо от­бросить, так как x_i&x_i x_i.

4) Если слагаемое В в ДНФ А содержит конъюнк­цию , то это слагаемое можно отбросить, так как , и следовательно, В 0, а ложное высказыва­ние из дизъюнкции можно выбросить (в силу равносиль­ности ).

Определение 5. Элементарной дизъюнкцией п пере­менных называется дизъюнкция переменных или их от­рицаний.

Определение 6. Конъюнктивной нормальной формой (КНФ) формулы А называется равносильная ей форму­ла, представляющая собой конъюнкцию элементарных дизъюнкций.

Определение 7. Совершенной конъюнктивной нор­мальной формой формулы А (СКНФ А), называется КНФ А, удовлетворяющая четырем свойствам:

1) все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные;

2) все элементарные дизъюнкции, входящие в КНФ А, различны;

3) каждая элементарная дизъюнкция, входящая в КНФ А, содержит переменную один раз;

4) ни одна элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.

СКНФ А можно получить двумя способами: а) с по­мощью таблицы истинности (используя закон двойствен­ности СКНФ А = СДНФ А, получаем с помощью табли­цы истинности СДНФ А, и, взяв отрицание СДНФ А, получаем СКНФ А); б) с помощью равносильных преоб­разований.

Правило получения СКНФ из формулы А с помо­щью равносильных преобразований.

1. Для формулы А получаем любую КНФ.

2. Из КНФ А путем равносильных преобразований получаем СКНФ А, последовательно добиваясь выпол­нения четырех свойств СКНФ.

1) Если элементарная дизъюнкция В, входящая в КНФ А, не содержит переменную x_i, тогда заменяем В на .

2) Если в некоторую элементарную дизъюнкцию В переменная x_t входит дважды, то лишнюю переменную

нужно отбросить, так как .

3) Если КНФ А содержит две одинаковых элемен­тарных дизъюнкции, то одну можно отбросить, так как .

4) Если в элементарную дизъюнкцию входит пара , то ее можно отбросить, так как , а ис­тинное высказывание из конъюнкции можно выбросить (в силу равносильности ).

Пример 1. Найти формулу, определяющую функ­цию Ф(х,у,z), по заданной таблице истинности:

х	y	z	Ф(х,у,z)

Решение. Используя правило получения формулы алгебры логики из таблицы истинности для функции Ф(х,у,z), получим:

.

Упростив эту формулу, получим:

.

Таким образом, искомой формулой, определяющей функцию Ф(х,у,z), можно считать х yz, или , или какую-нибудь другую из равносильных им формул.

Пример 2. Следующую формулу привести к СДНФ, предварительно приведя ее равносильными преобразова­ниями к ДНФ: .

Решение.

Ответ: СДНФ .

Пример 3. Для формулы из примера 2 найти СДНФ путем составления таблицы истинности.

Решение. Составим таблицу истинности для форму­лы .

a	b	с	bc	ab		A

Тогда СДНФ .

Пример 4. Для формулы из примера 2 найти СКНФ путем равносильных преобразований, предварительно приведя ее к КНФ.

Решение. Из примера 2: . Далее КНФ А.

Ответ: .

Пример 5. Для формулы из примера 2 найти СКНФ, записав предварительно СДНФ ее отрицания, а потом воспользовавшиь формулой двойственности.

Решение. СКНФ .

Все формулы алгебры логики делятся на три клас­са: 1) тождественно истинные; 2) тождественно ложные; 3) выполнимые.

Формулу А называют выполнимой, если она прини­мает значение 1 хотя бы на одном наборе значений вхо­дящих в нее переменных и не является тождественно истинной.

Теорема. Для того, чтобы формула алгебры логики была тождественно истинна (ложна), необходимо и достаточно, чтобы любая элементарная дизъюнкция (конъюнкция), входящая в КНФ А (ДНФ А), содержала переменную и ее отрицание.

Пример 6. Будет ли формула тож­дественно истинной, тождественно ложной или выпол­нимой?

Решение. Приведем формулу к какой-либо нормаль­ной форме:

.

Полученная ДНФ не является тождественно ложной, так как каждая элементарная конъюнкция не содержит переменную и ее отрицание. Следовательно, исходная формула тождественно истинна или выполнима. Преоб­разуем данную формулу к КНФ.

.

Это произведение не является тождественно истин­ным, так как элементарная сумма не тождественно истинна. Таким образом, исходная формула не тождествен­но ложна и не тождественно истинна, следователь­но, она выполнима.

1.34. По таблицам истинности найдите формулы, оп­ределяющие функции F₁(x,y,z), F₂(x,y,z), F₃(x,y,z), F₄(x,y,z), и придайте им более простой вид:

x	y	z	F1(x,y,z)	F2(x,y, z)	F3(x, у, z)	F4(x, у, z)

1.35. Пусть F(l₁,l₂,l₃), - булева функция, которая принимает значение 1 тогда и только тогда, когда точно одна из переменных принимает значение 1. Составьте таблицу для функции F(l₁,l₂,l₃) и выразите эту функ­цию через основные логические операции.

1.36. Назовем функцией большинства l₁|l₂|l₃ булеву функцию от трех переменных, значение которой совпа­дает с тем значением, которое принимает большинство переменных.

а) Составьте таблицу, определяющую функцию боль­шинства и выразите эту функцию через основные опера­ции.

б) Упростите выражение l₁|l₂|l_3.

1.37. Булева функция F*(l₁,l₂,…l_n) называется двой­ственной по отношению к булевой функции F(l₁,l₂,…l_n), если

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

1.38. Булева функция F(l₁,l₂,…l_n) называется:

а) сохраняющей 0, если F(0,0,...,0) = 0;

б) сохраняющей 1, если F(l,l,...,l) = 1.

Среди булевых функций от одной и двух перемен­ных найти все функции, сохраняющие 1, и все функ­ции, сохраняющие 0.

1.39. Для следующих формул найти СДНФ и СКНФ, каждую двумя способами (путем равносильных преобра­зований и используя таблицы истинности):

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) .

1.40. Найдите СДНФ для всякой тождественно ис­тинной формулы, содержащей: 1) одно переменное, 2) два переменных, 3) три переменных.

1.41. Найдите СКНФ для всякой тождественно лож­ной формулы, содержащей: 1) одно переменное, 2) два переменных, 3) три переменных.

1.42. Докажите равносильность формул и сравнением их совершенных нормальных форм (конъюнктивных или дизъюнктивных).

1.43. Найдите более простой вид формул, имеющих следующие совершенные нормальные формы:

1) ;

2) ;

3) ;

4) .

1.44. Используя критерий тождественной истиннос­ти и тождественной ложности формулы, установить бу­дет ли данная формула тождественно истинной, тожде­ственно ложной или выполнимой:

1) ;

2)

3) ;

4) ;

5) ;

6) .

Приложения алгебры логики

I. Приложение алгебры высказываний к релейно-контактным схемам (РКС).

Релейно-контактные схемы (их часто называют пе­реключательными схемами) широко используются в тех­нике автоматического управления.

Под переключательной схемой понимают схемати­ческое изображение некоторого устройства, состоящее из следующих элементов:

1) переключателей, которыми могут быть механи­ческие устройства, электромагнитные реле, полупровод­ники и т.д.;

2) соединяющие их проводники;

3) входы в схему и выходы из нее (клеммы, на кото­рые подается электрическое напряжение). Они называ­ются полюсами.

Простейшая схема содержит один переключатель Р и имеет один вход А и один выход В. Переключателю Р поставим в соответствие высказывание р, гласящее: «Пе­реключатель Р замкнут». Если р истинно, то импульс, поступающий на полюс А, может быть снят на полюсе В

без потери напряжения, т.е. схема пропускает ток. Если р ложно, то переключатель разомкнут, и схема тока не проводит. Таким образом, если принять во внимание не смысл высказывания, а только его значение, то можно считать, что любому высказыванию может быть постав­лена в соответствие переключательная схема с двумя полюсами (двухполюсная схема).

Формулам, включающим основные логические опе­рации, также могут быть поставлены в соответствие пе­реключательные схемы.

Так, конъюнкции двух высказываний p&q ставит­ся в соответствие схема:

а дизъюнкции схема:

Т.к. любая формула алгебры логики может быть запи­сана в ДНФ или КНФ, то ясно, что каждой формуле алгеб­ры логики можно поставить в соответствие некоторую РКС, а каждой РКС можно поставить в соответствие некоторую формулу алгебры логики. Поэтому возможности схемы можно выявить, изучая соответствующую ей формулу, а упрощение схемы можно свести к упрощению формулы.

Пример 1. Составить РКС для формулы .

Решение. Упростим данную формулу с помощью равносильных преобразований:

.

Тогда РКС для данной формулы имеет вид*:

Пример 2. Упростить РКС:

Решение. Составим по данной РКС формулу (функ­цию проводимости) и упростим ее:

(к последним двум слагаемым применили закон погло­щения).

Тогда упрощенная схема выглядит так: