Практическое занятие №11

Тема: Полные системы связок

Продолжительность 2 часа

Цель: изучить понятие представления одной связки в терминах других связок, научиться решать задачи на полные системы связок.

Задачи. 1. Пусть x * y =Ø(x Þ y) x Å y =Ø(x Û y). Докажите, что одна из систем связок {Û, *} и {Û, Å} – полная, а другая – нет.

2. Задачапо книге [2]: 6.1 (а)-(д) на стр. 123.

3. Задачапо книге [2]: 6.2 (а)-(д) на стр. 123.

Указания к решению задач.

1. Решение. 1) Полнота системы связок {Ø, Ú} означает, что любая булева функция определима в терминах Ø и Ú. Связки Ø и Ú определимы в терминах Û и *: 0= x * x, Ø x = x Û0, x Ú y =Ø x Þ y =Ø(Ø x Þ y).

Следовательно, любая булева функция определима в терминах Û и *, т.е. {Û, *} – полная система связок.

2) x Û x =1, x Å x =0, x Û1= x, x Û0=Ø x, x Å1=Ø x, x Å0= x, т.е. при помощи связок Û и Å, исходя из одной переменной x, можно получить только 0, 1, x и Ø x. По таблице истинности легко проверить, что x Û(x Û y)= y, x Û(x Å y)=Ø y, x Å(x Å y)= y, x Û(x Å y)=Ø y. Значит, исходя из двух переменных, при помощи связок Û и Å можно получить 0, 1, переменные, отрицания переменных, те же самые функции x Û y и x Å y. А, например, дизъюнкция x Ú y не может быть определена в терминах Û и Å.

Следовательно, система связок {Ù, Å} не полная.

2. Посмотреть решение 6.1 (д), (л) на стр. 123 книги [2].

3. Посмотреть решение 6.2 (а), (л) на стр. 123 книги [2].

Самостоятельно:

2. Задачапо книге [2]: 6.1 (е)-(л) на стр. 123.

3. Задачапо книге [2]: 6.2 (е)-(л) на стр. 123.