21

Часть 2. Математическая логика

ЗАНЯТИЕ 1.

Логика высказываний

Будут использоваться большие латинские буквы А, В, С, … для обозначения произвольных пропозициональных переменных, а большие готические буквы , ς ,… для обозначения формул.

Понятие формулы алгебры высказываний определяется следующим образом:

1.пропозициональная переменная есть формула;

2.если и В – формулы, то , ( & В ), ( В ), ( В )—формулы;

3.других формул, кроме построенных по пп. 1), 2), нет.

Будем интерпретировать логические связки как функции, определенные на множестве {1 ,0} (истина, ложь), со значениями в том же множестве следующим образом.

Отрицание : 1 = 0, 0 = 1.

Конъюнкция: 1 & 1 = 1, 1 & 0 = 0, 0 & 1 = 0, 0 & 0 =0. Дизъюнкция: 1 1 = 1, 1 0 = 0, 0 1 = 1, 0 0 = 0. Импликация: 1 1 = 1, 0 1 = 0, 0 0 = 1, 1 0 = 1.

Исключающее или : (А& B) ( A&B).

Тогда каждая формула будет интерпретироваться как функция, определенная на множестве {1,0}, со значениями в этом же множестве, полученная из , & , , по правилам построения данной формулы. Такую функцию будем называть таблицей истинности данной формулы. Значением формулы при данных значениях переменных в множестве {1, 0} называется значение функции, соответствующей формуле , при этих значениях переменных.

Переменная xi называется фиктивной (несущественной) переменной функции f(x1,···,xn),

если

f(x1,···,xi-1,0,xi+1,···,xn) = f(x1,···,xi-1,1,xi+1,···,xn)

для любых значений x1,···,xi-1,xi+1,···,xn. Иначе переменная xi называется существенной.

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

Задачи:

1.Сколько функций от 2-х переменных существенно зависят от этих переменных?

2.Укажите фиктивные переменные функции f(x,y,z), заданной вектором значений: f = (1,1,1,1,0,0,0,0)

f = (0,0,1,1,0,0,1,1) f = (0,0,1,1,1,1,0,0)

3.Найдите количество функций n переменных, принимающих значение 1 ровно на одном наборе.

4.Найдите количество функций n переменных, принимающих на противоположных наборах одинаковые значения.

5.Сколько имеется различных функций от n переменных, сохраняющих 0, т.е. равных нулю на нулевом наборе: f

(0, … ,0) = 0.

6.Является ли формулой ¬(p & q)?

22

7.Является ли формулой (p)?

8.Определить, являются ли следующие формулы тавтологиями: (x→y)→((y→z)→(x→z));

(x→y)→((z→y)→(x z→y)); (x→(y→z))→((x→y)→(x→z)); (¬x→¬y)→(x→y). ((a→b)→a)→((a→b)→b); (a→c)→(a→b c); (¬a→b)→(¬b→a); ((a→b)→(a→c))→((a→(b→c)); (b→c)→(b→(a→c)); (b→a)→(a b→a); a&b→(c→b);

(b→a c)→((b→c)→((d→c)→(b d→c))); ((b→a)→c)→(a→c); a&b c&d→(a b)&(c d); (a→b)&(c→d)→(a c→b d); (a b→c)→(a→c) (b→c); (a&b→c)→((a→c)→(b→c)); (a→b)&(c→d)→(a&c→b&d).

9.Проверить, являются ли эквивалентными следующие формулы:

а) A≡(A B) и A B; б) A→B и ¬A B;

в) A≡B,¬A¬B AB и (A ¬B)(¬A B); г) A B и ¬AB ¬BA.

10.Проверить полноту систем функций: {x y, x y, 1}

{xy xz yz, x} {x≡y, x y, 0} {0, 1, (x→y)→z} {xy, (x≡y)≡z}

11.Построить таблицы истинности на области интерпретации D={1, 2}:

X y(P(x) Q(y)→R)x( y(R→P(x) Q(y))x(R→ y(P(x)→Q(y)))x(R→ y(Q(y)→P(x)))x(P(x)→ y(R→Q(y)))x(P(x)→ y(Q(y)→P(x)))x y(P(x) Q(y)→Q(y))x(P(x)& y(Q(y)→R))x(P(x) y(Q(y)→R)→S)x(P(x)& yQ(y))→ xP(x)X y(P(x) Q(y)→R)x( y(R→P(x) Q(y))x(R→ y(P(x)→Q(y)))x(R→ y(Q(y)→P(x)))x(P(x)→ y(R→Q(y)))x(P(x)→ y(Q(y)→P(x)))x y(P(x) Q(y)→Q(y))x(P(x)& y(Q(y)→R))x(P(x) y(Q(y)→R)→S)x(P(x)& yQ(y))→ xP(x)X y(P(x) Q(y)→R)x( y(R→P(x) Q(y))x(R→ y(P(x)→Q(y)))x(R→ y(Q(y)→P(x)))x(P(x)→ y(R→Q(y)))x(P(x)→ y(Q(y)→P(x)))