Практическое занятие №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.

Практическое занятие №12 Тема: Построение выводов теорем

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

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

Задачи. 1. Упражнения 1-2 на стр. 40 по книге [1].

2. Упражнения 1-2 на стр. 43 по книге [1].

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

1. Посмотреть примеры доказательства теорем на стр. 41-42 книги [1].

Самостоятельно: Упражнения 3-4 на стр. 40 по книге [1].

Практическое занятие №13 Тема: Независимость аксиом исчисления высказываний

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

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

Задачи. 1. Доказать независимость аксиомы (А1) ([1], стр.46).

2. Доказать независимость аксиомы (А2) ([1], стр.47).

3. Доказать независимость аксиомы (А3) методом стирания всех отрицаний ([1], стр.47).

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

1. Построить таблицы для операций отрицания и импликации на множестве 0, 1, н так, что (А2), (А3) равны 1, и если условия правила МР равны 1, то его заключение тоже равно 1, но (А1) может быть равно 0 или н.

2. Построить таблицы для операций отрицания и импликации на множестве 0, 1, н так, что (А1), (А3) равны 1, и если условия правила МР равны 1, то его заключение тоже равно 1, но (А2) может быть равно 0 или н.

Самостоятельно: Доказать независимость аксиомы (А3) ([1], упражнение на стр.47).

Практическое занятие №14 Тема: Операции над предикатами

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

Цель: усвоить понятие n-местного предиката, множества истинности предиката, логических операций над предикатами.

Задачи. 1. Упражнение 9.1 (а)-(д) на стр. 168 книги [2].

2. Упражнение 9.6 (а)-(д) на стр. 164 книги [2].

3. Упражнение 9.15 (а)-(д) на стр. 164 книги [2].

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

3. (а) Обозначим через A, B, C множества истинности предикатов P(x), Q(x), P(x) соответствено. Тогда множество истинности предиката

есть множество , отсюда, применяя дистрибутивность пересечения относительно объединения, находим множество

.

Самостоятельно. 1. Упражнение 9.1 (е)-(з) на стр. 168 книги [2].

2. Упражнение 9.6 (е)-(з) на стр. 164 книги [2].

3. Упражнение 9.15 (е)-(з) на стр. 164 книги [2].