Свойства операций и отношений

Свойства операций и отношений

2) ,

3)

4) A  A  B, A  B  A, A \ B  A, A  A = A, A  A = A,

5) A  B  A  B = B  A  B = A

6. 
   A  B & C  D  A  C  B  D
   
7. 
   A  B & C  D  A  C  B  D
   
8. 
   A  B & C  D  A \ D  B \ C
   

Можно заметить, что существует тесная связь, между множествами и высказываниями, между операциями над множествами и логическими опе рациями. Пусть мы имеем несколько высказываний. Образуем множество всех логических возможностей для рассматриваемых высказываний и на зовем его универсальным множеством. Поставим каждому высказыванию в соответствие подмножество тех логических возможностей универсального множества, для которых это высказывание истинно - его множество истин

ности. Очевидно, что множествами истинности высказываний P&Q, P  Q,  P будут, соответственно, множества PQ, PQ, P, где P, Q– множества

истинности высказываний P, Q.

Пусть булева функция f(x₁,...,x_n ) представима термом, содержащим только логические символы &, ,  . Обозначим через f^ (x) формулу теории множеств, полученную из терма f подстановками вместо переменных x₁,..., x_n формул x  A₁,..., x  A_n , соответственно. Обозначим через Z_f выражение, полученное из терма для f(x₁,..., x_n) заменой переменных x₁,...,x_n символами Z₁,...,Z_n, и символов &, ,  символами , , , соответственно. При интерпретации Z_f символы Z_i будут обозначать подмножества универсума U (множества, содержащего в качестве подмножеств все другие множества).
Упражнение

1. Доказать, пользуясь кругами Эйлера, что высказывание P & Q  Q

является тавтологией.

2. Используя истинностные таблицы соответствующих высказываний, проверить следующее свойство множеств: A(BC) = (AB)( AC).

3. 
   Отношения – это множества, элементами которых являются упорядочен
   

3.1. Для формул исчисления высказываний: если A  B и B С, то AC.

2. 
   Отношение логического следования не является симметричным:
   

2. 
   Отношение “x делит y” (обозначается “x  y”) антисимметрично:
   

2. 
   Если прямая L параллельна прямой L’ и прямая L’ параллельна
   

2. 
   Доказать,что симметричное и транзитивное отношение рефлексивно
   

(Требования, которым должны удовлетворять правила вывода, – из истинных посылок должны получаться истинные заключения.)

Д о к а з а т е л ь с т в о м ф о р м у л ы Ф (т е о р е м ы) называют конечный список формул B₁,...,B_l, заканчивающийся формулой Ф (Ф = B_l), где каждая формула B_i (i=1,...,l) есть аксиома или получена из предыдущих формул по одному из правил вывода (обозначается Ф).

Пример 1 (Доказательство теоремы).

AA :

2. A((AA) A) (аксиома 1а)

3. (A(AA))((A((AA)A))(AA)) (аксиома 1б)

4. (A((AA)A))(AA) (modus ponens, 2,3)

5. AA (modus ponens, 1,4)
В ы в о д о м ф о р м у л ы Ф и з г и п о т е з A₁, ..., A_m (m  1) называют конечный список формул B₁,...,B_l, заканчивающийся формулой Ф (Ф = B_l), где каждая формула B_i (i=1,...,l) есть аксиома или одна из гипотез A₁,... ,A_m,

или получена из предыдущих формул по правилу вывода ( A₁,... ,A_m Ф).

1. A&BC (гипотеза)

2. (BA&B)  ((B(A&BC)) (BC)) (аксиома 1б)

3. (A&BC) (B(A&BC)) (аксиома 1а)

4. B(A&BC) (modus ponens,1,3)

5. A (гипотеза)

6. A (BA&B) (аксиома 2)

7. BA&B (modus ponens,5,6)

8. (B(A&BC)) (BC) (modus ponens,7,2)

9. BC (modus ponens,4,8)

1. A₁,...,A_m _i (i=)

 ₁,...,A_m _j (j=) и B₁,...,B_k C  A₁,...,A_m C

3. 
   A₁,... ,A_i, ..., A_j, ..., A_m B  A₁,...,A_j, ..., A_i, ..., A_m B.
   
4. 
   A₁, ..., A_m B  A₁, ..., A_m , A_m+1B.