Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Критерии полноты Поста-Яблонского




Теорема о функциональной полноте была сформулирована в 1921 г. американским ученым Эмилем Постом и доказана советским ученым Яблонским С.В.

Система S булевых функций fi является полной тогда и только тог­да, когда выполняются 5 условий: существует функция fi Î S, не сохра­няющая константу нуль: fi Ï K0; функция fi Î S, не сохраняющая констан­ту 1: fi Ï K1; нелинейная функция, не самодвойственная и немонотонная функция в системе S. Построим все булевы функции от двух переменных (табл.).

переменные булевы функции
X1 X2 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15

Индекс i функциональной переменной равен десятичному эквиваленту этой функции, читаемому сверху вниз.

- константа 0

- конъюнкция

- левая коимпликация (читается “неправда, что если X1 то X2», префикс ко – от латинского conversus - обратный

- правая коимпликация

- сложение по модулю 2 (неравнозначность)

- дизъюнкция

- стрелка Пирса, функция Вебба

- эквивалентность

- отрицание X2

- правая импликация («если X1 то X2»)

- отрицание X1 («если X1 то X2»)

- левая импликация

- штрих Шеффера

Для порождения всех базисов в P2 построим двумерную таблицу, каж­дой строке которой взаимно однозначно составим 11 функций, столбцу - класс, и в клетке (i, j) ставим 1, если 1 -функция не принадлежит j классу.

идентификатор строки номер функции fi классы
K0 K1 Kл Kс Kм
a      
b      
c  
d    
e      
g
k    
m    
n  
p
r      

Из таблицы видно, что каждое, указанное ниже, покрытие порождает базис Bi.

П1 = {g} Û B1 – базис Вебба;

П2 = {p} Û B2 – базис Шеффера;

П3 = {a, n} Û B3 = {Þ, 0} – импликативный базис;

П4 = {b, m} Û B4 = {& Ø} – конъюнктивный базис Буля;

П5 = {m, e} Û B5 = {Ú Ø} – дизъюнктивный базис Буля;

П6 = {r, b, d} Û B6 = {Å, &, 1} – базис Жегалкина;

П7 = {m, n} Û B7 = {Þ , Ø} – базис Фреге.

Всего 17 базисов.

Наиболее часто приходится использовать базис Шеффера.

Вопросы для самопроверки

1. Составьте таблицы истинности для формул:

а) б)

в) г)

д)

x y

 

3.2. Установите с помощью таблиц истинности какие из следующих формул - тавтологии:

а) б)

в) г)

д) е)

3. На основании каких законов логики получены следующие соотношения? Докажите их с помощью таблиц истинности :

; ; ; ; ; ; ; ; ; ; ; ;

4. Какие из данных формул равносильны:

а) б) в) г)

д) е) ж) з)

5. Полиция задержала 4 гангстеров, подозреваемых в краже автомобиля: Анри, Луи, Жоржа и Тома. При допросе они дали следующие показания: Анри: «Это был Луи», Луи: «Это сделал Том», Жорж: «Это не я», Том: «Луи лжет, говоря, что это я». Дополнительное расследование показало, что правду сказал только один из них. Кто украл машину?

х y z F1 F2

Таблица к задаче 6

6. Составьте формулы, соответствующие данной таблице истинности (выберите рациональный способ). Упростите полученные формулы и изобразитеих в виде контактных схем.

7. Для каждой из данных формул найдите ее СДНФ и СКНФ:

а) б) в)

г)

8. Напишите СДНФ представляющую: а) тавтологии с переменными х и у; б) тавтологии с переменными х, у и а; в) тождественно ложные формулы с переменными х, у и а.

Пример: .

9. Составьте всевозможные таблицы истинности для формул с 2 переменными х и у. Выпишите СДНФ и СКНФ формул, соответствую­щих этим таблицам. Укажите 16 таких таблиц.

10. Один логик попал в плен дикарям в пещеру, имеющую 2 выхода. Вождь дикарей предложил логику следующий шанс на спасение: «Один выход ведет на свободу, другой на смерть. Сделать выбор тебе помогут два моих воина, одному из которых ты можешь задать единственный вопрос. Но предупреждаю тебя, что один из этих воинов всегда говорит правду, а другой всегда лжет». Что должен спросить логик?

11. Установите, какие из данных формул являются ДНФ, СДНФ, УНФ и СКНФ формул с переменными х, у и z:

а) б) в)

г) д) е)

ж)

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

.

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

а) б) в)

г) д) е)

13. Приведите следующие формулы к СКНФ с помощью равносильных преобразований и проверьте их с помощью таблиц истинности :

а) б) в)

г) д)

Примечание: .

14. Найти все булевы функции от 2х переменных являющиеся:

а) линейными; б) монотонными; в) самодвойственными.

15. Установить является ли самодвойственной функция эквивалентности.

16. Привести пример монотонной функции, которая одновременно была бы линейной.

17. Убедиться, что функции Шеффера и Вебба не являются ни линейными, ни монотонными.


 

 





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:



©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.