Формальная логика

Т а в т о л о г и я (общезначимая формула, логический закон) - формула, истинная при всех интерпретациях входящих в нее пропозициональных букв, другими словами, - столбец значений которой содержит одни истинные значения (обозначается знаком =).

1. Построить таблицы истинности следующих формул:

1. 
   (Р&(QP))&((QP)Q);
   
2. 
   P&(Q&(PQ));
   
3. 
   ((PQ)R)&(RQ).
   

1. 
   PP (закон исключенного третьего);
   
2. 
   (P&P) (закон отрицания противоречия);
   
3. 
   PP (закон двойного отрицания);
   
4. 
   PP (закон тождества);
   
5. 
   (P&P) P (идемпотентность конъюнкции);
   
6. 
   (PP) P (идемпотентность дизъюнкции);
   
7. 
   (P&Q) (Q&P) (коммутативность конъюнкции);
   
8. 
   (PQ) (QP) (коммутативность дизъюнкции);
   
9. 
   ((P&Q)&R) (P&(Q&R)) (ассоциативность конъюнкции);
   
10. 
    ((PQ)R)  (P(QR)) (ассоциативность дизъюнкции);
    
11. 
    (P&(QR))((P&Q)(P&R)) (первый закон дистрибутивности);
    
12. 
    (P(Q&R))((PQ)&(PR)) (второй закон дистрибутивности);
    
13. 
    (P&(QP))  P (1-й закон погощения);
    

p) (P&Q)(PQ) (1-й закон де Моргана);

q) (PQ)(P&Q) (2-й закон де Моргана).

3. Выяснить, справедливы ли следующие утверждения:

1. 
    A B тогда и только тогда, когда  A или  B;
   
2. 
    A B тогда и только тогда, когда  A и  B;
   
3. 
    A&B тогда и только тогда, когда  A и  B;
   
4. 
    A&B тогда и только тогда, когда  A или  B;
   
5. 
    A  B тогда и только тогда, когда  B.
   

общезначима формула E(P,Q) =P&Q  P.

Поэтому в истинностной таблице на входы можно помещать метабуквы.

ТЕОРЕМА 2. (Основные тавтологии).

1а. |=A(BA)

1б. |=(AB)((A(BC))(AC))

2. |=A(BA&B)

3а. |=A&BA

3б. |=A&BB

4а. |=AAB

4б. |=BAB

5. |=(AC)((BC)(ABC))

6. |=(AC)((AC) A)

7. |=AA

8. |=(AB)((BA)(AB))

9а. |=(AB)(AB)

9б. |=(AB)(BA)

10. |=(A(AC)

Д о к а з а т е л ь с т в о. Применяем теорему 1 и таблицы истинности формул.

ТЕОРЕМА 3. Если |= A и = A  B, то = B.

Д о к а з а т е л ь с т в о. Пусть = A и = A  B и P₁, ... , P_n - все переменные, входящие в эти формулы. Допустим противное, что при некоторой интерпретации  : {P₁, ... , P_n}  {И,Л}, B[] = Л. По условию, для всех интерпретаций, в частности, для интерпретации  , A[] = И и (A B)[] = И, что однако противоречит определению операции .

Д о к а з а т е л ь с т в о. Для всех интерпретаций  пропозициональных букв, (A B)[] =И т.и т.т., когда A[] = B[]. Откуда следует утверждение теоремы.

Д о к а з а т е л ь с т в о получается с помощью теоремы 4.

((PS)Q)&S((SRQ) P) 

((PS Q) &(QPS)&S)   (  S  R Q P) 

 ((PS Q) &(QPS)&S)   (  S  R Q P) 

 (( (PS)  Q) & ( Q  P  S) &  S)   (  S  R Q P) 

( (PS)  Q)  (Q  P  S)  S)  (S &  R &  Q &  P) 

((P S) & Q)  (Q&P&S)  S  (S &  R &  Q &  P) 

(P&Q)  (S&Q) (Q&P&S)  S  (P&Q)  (Q&P&S)  S 

(P&Q)  ((Q  S )&(P S)&(S S))  (P&Q)  (Q&P) S.
Формула называется формулой с тесными отрицаниями, если операция  применяется только к атомам.

ТЕОРЕМА 6. Пусть Е формула с тесными отрицаниями, не содержащая других операций, кроме , , . Формула E^X есть результат замены в E (на всех местах) конъюнкции на дизъюнкцию, дизъюнкции на конъюнкцию и каждой пропозициональной буквы на ее отрицание. Тогда |= Е ~ Е^X.

Д о к а з а т е л ь с т в о теоремы проведем индукцией по построению фор мулы E. Базис индукции: ЕР : Е Р и, по определению оперaции ‘X’, Е^Х  Р, ч.т.д. Индукционный шаг : а) E  АB, b) E  АB, c) E A..

1. 
   EАB: = Е  ( АB) (по закону де Моргана) AB  (по индукционному допущению и теореме 5) A^X  B^X  (по определению операции ‘крест’) (АB)^Х  Е^Х.
   
2. 
   EAB: = E  (AB) (по закону де Моргана и теореме 5) A&B  (по индукционному допущению и теореме 5) A^X&B^X  (по определению операции ‘крест’) (AB)^X  E^X.
   
3. 
   EA: тогда AP, EPP и E^XP, ч.т.д.
   

1. 
   Если =  E, то = E. b) Если = E, то =  E.
   

Д о к а з а т е л ь с т в о.

a): =  E (допущение)

= E  E^X (теорема 6)

= E^X (следствие из теоремы 5)

= (E^X)^P_P (теорема 1);

= ((E^X)^P_P)^P_P (следствие из теоремы 5),т.е. = E.

b): = E (допущение)

=  E (следствие теоремы 5)

= (E)  (E^X ) (теорема 6 и теорема 5)

= (E^X ) (следствие из теоремы 5)

= ((E^X))^P_P (теорема 1)

= (E^X)^P_P (по определению операции подстановки)

= ((E^X)^P_P)^P_P (следствие из теоремы 5)

=  ((E^X)^P_P)^P_P (по определению операции замены), т.е. =  E ^.
Назовем формулу B логическим следствием формул A₁,A₂,...,A_m (m1)

(обозначается A₁,A₂,...,A_m=B), если в таблице истинности в строках, где формулы A₁,A₂,...,A_m (посылки) одновременно истинны, истинна также и формула B (заключение).

ТЕОРЕМА 8. a) A = B т.и т.т., когда = A  B.

b) A₁,A₂,...,A_m-1,A_m = B т.и т.т., когда A₁,A₂,...,A_m-1 = A_mB (m1).

(m1).

1. 
   Применяя теорему 5 и известные эквивалентности, упростить формулы:
   

1. 
   (AB)(AB); b) (AB)&(B A)&(CA); c)(AB)((AB)A).
   

2. 
   Методом от противного проверьте, верны ли следующие отношения логического следования:
   

b) F (K  M), (H  L)  Q, QF  (FL)  M.

3. Применяя теорему 5, упростить следующие формулы:

a) ((P  Q)&(Q  P)); b) (P&Q)  ( (P  Q)&P);

c) (P  Q)&(PQ); d) (P  Q)&(Q  P)&(R  P).

4. Выяснить, какие из формул G_i (i=1,…,11) являются логическими следствиями формул F₁, F₂, F₃ ?

5.Расположите формулы так, чтобы из каждой логически следовали все, стоящие после нее:

a) PQ, (P(QP)), (P&Q), PQ, P&Q;

b) PQ, P&Q, P(Q(P&Q)), QP, PQ;

c) (PQ)P, (PQ)&(QP), (PQ), (P&Q), P&Q.

6. Докажите следующие утверждения:

a) Если A, B  C и  A, то B  C.

b) Если A  B и A   B, то  A.

c) Если  A, то для любой формулы B верно B  A.

7. Какой из формул, записанных под чертой, эквивалентна формула над чертой: a) P  Q

P& Q, PQ, (P& Q), Q& P, QP.

b) (P  Q)  (P  Q)

P  Q, PQ, (PQ)  P, PQ, P  (QP)

c) PQ

n-местная операция на множестве {0,1}.

А л ф а в и т: (1) x,y,...,x₁,x₂,... - предметные переменные;

(2) f,g,...,f₁,f₂,... функциональные символы.

Т е р м: (1) x,y,...,x₁,x₂,... - предметные переменные являются термами;

(2) если f^{( n)} -функциональный символ, t₁,...,t_n - термы, то f^{( n)} (t₁,...,t_n) - терм.

(2) если t = f ⁽ⁿ⁾ (t₁,...,t_n ) , то зн t = f ⁽ⁿ⁾ (зн t₁,..., зн t_n).

{v₁, ..., v_m}  {x₁,...,x_n} и t  = f ⁽ⁿ⁾  для всех интерпретаций

 : {x₁,...,x_n}  {0,1}.

ТЕОРЕМА. Для каждой формулы A алгебры высказываний существует

функция алгебры высказываний f (A) такая, что A₁  A₂  f(A₁) = f(A₂).

термом, все функциональные символы которого содержатся среди f ₁,...,f_m.

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

Д о к а з а т е л ь с т в о теоремы следует из более общей формулы разложения функции по части входящих в нее переменных :

f(x₁,...,x_n ) =  x₁^1 &...&x_m^m & f(₁,...,_m, x_m+1,...,x_n),

(₁,...,_m)

где _i  {0,1}, x_i⁰ ₌ x_i, x_i¹ = x_i (i = 1,...,m).

В частности, f(x₁,...,x_n ) =  x₁^1 &...&x_n^n .

(₁,...,n)

f(₁,...,_n) = 1

1. Воспользовавшись формулой, разложить функцию (xy&z)&x по переменным x, z.

(xy&z)&x = (x⁰&z⁰&((0y&0)&0))(x⁰&z¹&((0y&1)&0))

(x¹&z⁰&((1y&0)&1))(x¹&z¹&((1y&1)&1)) =

= (x&z&o)(x&z&0)(x&z&0)(x&z&y) = (x&y&z) .

2. Используя истинностную таблицу функции f = (11100101), получить

ее с.д.н.ф.

Решение:

x	y	z	f
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

f(x,y,z) = (x&y&z)(x&y&z)(x&y&z) (x&y&z)(x&y&z).

f(x₁,...,x_n ) = & x₁ ^1  ... x_n ^n ,

(₁,...,_n)

f (₁,...,_n) = 0

где _i  {0,1}, x_i⁰ = x_i, x_i¹ = x_i (i = 1,...,n).

Метод синтеза релейно - контактных схем
Проинтерпретируем булевы функции как электрические сети, содержа-

щие двухпозиционные переключатели x,  x - соответственно, замыкаю-

щий и размыкающий контакты; &,  - соответственно, последовательное и параллельное соединения контактов; 1 и 0 - соответственно, «ток прохо- дит» и «ток не проходит». Две цепи называются эквивалентными, если через одну из них ток проходит т.и т.т, когда он проходит через другую.

Пример 1. Упростить следующую релейно-контактную схему, получив ее функцию проводимости, и минимизировать ее.
x y

z

x

z

y
Решение: (x,y,z) = (x& y)  z ((x y)&z)) = (x& y)  z

x  y



z
Пример 2. Используя с.д.н.ф.(с.к.н.ф.), найти формулу для функции про

водимости f и начертить соответствующую ей релейно-контактную схе-

му, если f(1,0,0,0) = f(1,1,0,0) = f(0,1,1,0) = 1.

Решение: f(x,y,z,u) = (x&y&z&u) (x&y&z&u) (x&y&z&u) =

((x&z&u)&( yy))  (x&y&z&u) = (x&z&u)  (x&y&z&u)= .

((x&z)  (x&y&z))&u.

x  z

u

 x y z
Пример 3. Имеется одна лампочка в лестничном пролете двухэтажного дома. Постройте схему так, чтобы на каждом этаже своим выключателем можно было бы гасить и зажигать лампочку.

Решение. Функция проводимости такой схемы меняет свои значения, если меняет значение один из ее аргументов: f(0,0) = f(1,1) = 1, f(0,1) = f(1,0) = 0.

Воспользовавшись с.д.н.ф., получим функцию f(x,y) = (x&y)(x&y).

Имеются два способа задания множеств: (1) путем явного перечисления

его элементов, например, целые числа между 0 и 5, т.е. {0,1,2,3,4,5};

(2) указанием свойства, определяющего принадлежность элемента данному множеству, т.е. {x;  (x)}.

Рассмотрим язык, предназначенный для описания свойств множеств.

А л ф а в и т содержит переменные x,y,z,..., пробегающие множества,

символ принадлежности ‘’ и символы логики высказываний.

Т е р м ы и ф о р м у л ы определим одновременно:

1. 
   x,y,z,... - предметные переменные, пробегающие множества, - термы;
   
2. 
   если t, r - термы, то t r элементарная формула (атом) ;
   
3. 
   если ,  - формулы, то &, , ,   ,   - формулы;
   
4. 
   если x - переменная, и  - формула, то {x; (x)} - терм.
   

Определим операции (пересечение, объединение, разность, дополнение) и отношения (включение, равенство) над множествами (для удобства объекты-множества будем обозначать заглавными буквами, а объекты, являющиеся элементами множеств, малыми буквами):

A

B

A

B

A

B

4. A  B  ¹⁾x (x  A  x  B)

5. A = B  x (x  A  x  B)

6. U = {x : x = x},  = {x : x  x}

7.

(перечеркнутые символы = и  означают, что соответствующие = - и  - отношения не имеют места).