2020-07-12
183
1. Выбрать в таблице задания функции все наборы (
) аргументов, на которых 
.
2. Выписать конституенты единицы 
, соответствующие этим наборам аргументов; при этом, если аргумент 
входит в данный набор как 1, он вписывается без изменений в конъюнкт 
; если же 
входит в данный набор как 0, то в соответствующий конъюнкт вписывается его отрицание (
).
3. Все полученные конституенты единицы соединяются знаками дизъюнкции.
Пример 1-9. Найти СДНФ и СКНФ функции 
, заданной следующей таблицей истинности:
| 
| 
| 
| Конституенты: 
|
| 0 | 0 | 0 | 1 | 
|
| 0 | 0 | 1 | 1 | 
|
| 0 | 1 | 0 | 0 | 
|
| 0 | 1 | 1 | 0 | 
|
| 1 | 0 | 0 | 0 | 
|
| 1 | 0 | 1 | 1 | 
|
| 1 | 1 | 0 | 0 | 
|
| 1 | 1 | 1 | 1 | 
|
(
) – наборы аргументов 
.
|
|
2.2 ЗАДАЧИ И УПРАЖНЕНИЯ IIГО – ТИПА *.
1. Проверить полноту заданной системы функций. Для функционально полной системы выделить базис.
1) F={ 
, 
}, где =x 
y, =x yz,
2) F={ , , 
, 
}, где =xy, =x~yz, =0, =1,
3) F={ , , , }, где =(x y) 
(y~z), =(x/(xy)) 
z, =x 
y,
=0,
4) F={ , , }, где =(0110 1001), =(1000 1101), =(0001 1100)
5) F={ , , }, где =(0100 0100), =(1111 1100), =(1000 0000)
2. Составить все возможные базисы из функций двух переменных.
3. Для заданной функции 
:
1) построить таблицу истинности;
2) построить изображение на кубе;
З) найти СДНФ и СКНФ;
4. Определить принадлежность классам Поста.
5. Построить функционально полную систему функции так, чтобы эта система была базисом и содержала 
.
=x 
p/z 
y 
x p z 
x y z,
=p 
y y x 
z 
p/y z x,
==p/z x y z 
y 
p x y 
z,
=y z p x z p y/y 
z,
=z y p x z p/z y x,
=x y p x z x/y z x 
z,
=z y x z 
p 
x z/y 
p,
=y z p x z p y/p z,
=p x z y p z y/z x,
=x/y z p x y z p y z,
=z 
p y z x p y z/x,
=x/z p y x z p z p,
=x y 
z p x/y 
z 
p z,
Пусть (
) – набор логических переменных, 
- набор нулей и единиц.
Конституентой единиц набора 
называется конъюнкт:
.
Конституентой нуля набора называется дизъюнкт:
.
Отметим, что 
(
) тогда и только тогда, когда 
.
Совершенной ДНФ называется дизъюнкция некоторых конституент единиц, среди которых нет одинаковых, а совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждой конъюнкт (дизъюнкт) каждая переменная 
из набора (
) входит ровно один раз, причем входит либо сама 
, либо ее отрицание 
.
Пример 1-8. Формула 
есть конституента единицы 
; формула 
есть конституента нуля 
; формула 
- СДНФ, формула (
) 
- СКНФ.
Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исходной формуле 
, предварительно рассмотрим разложения булевой функции 
по 
переменным (для определенности по 
) –разложения Шеннона.
Теорема 4 (первая теорема Шеннона). Любая булева функция 
представима в виде разложения Шеннона:
.
при 
для булевой функции 
,получаем ее представление в виде совершенной ДНФ:
.
В силу принципа двойственности для булевых алгебр справедлива:
Теорема 5 (вторая теорема Шеннона). Любая булева функция 
представима в виде разложения Шеннона:
|
=y 
p x z p y/p 
x z,
=p x z y 
p/z y x 
y,
=x/p y x 
p 
z y z y,
=p z x y (z p x)/y 
p,
=z x y/x p x z p x,
=p x y z/p p x z y,
=z/p x p y x p y z,
=p x z y p z/x z y,
=x 
p z y z p/x z x,
=x z p/y z p y 
x z,
=x z p y/x p x y z,
=y p x/z y p x z x,
=p x y/z p x z y z,
=x y z p z y/z p x,
=y/z x p x z y z p,
=x y z x y p z y/x,
=z p x (p z)/z y p 
x,
=p/x z y x p z y x,
=x y z p x y z/p x,
=z p x y z p x y/x,
=p 
x z y/p x y p x,
=y x z p/y x p z,
=y x y p z/x y x z,
=x y z p x z y p/x,
=z/y p x y z x p y,
=y x p z x y/z p z,
=p x z y x z/p y 
x,
=x y z p/x y z p x,
|
=x y z p/x y z p x,
Функции дизъюнкции и конъюнкции могут быть выражены через импликацию следующим образом:
(1 – 19)
Для функций Шеффера и Вебба имеет место переместительный закон:
; 
.
Сочетательный закон для них несправедлив:
; 
Имеют место следующие очевидные соотношения:
(1 – 20)
Выражение функции Шеффера и Вебба в базисе { 
}:
(1 – 21)
Функции Шеффера и Вебба связаны между собой соотношениями, аналогичными формулам де Моргана для функций конъюнкции и дизъюнкции:
(1 – 22)
