цуимп / логика

Логика – наука о законах мышления. Она позволяет делать правильные выводы из любых посылок, предохраняет от ошибок в рассуждениях, обеспечивает безошибочное доказательство всевозможных законов, правил и теорем в различных областях знаний: в математике, физике, химии, в грамматике русского языка и т.п. Для решения этих задач используется алгебра логики.  В алгебре логики (булевой алгебре) переменные могут принимать два значения: 1 (истинно) или 0 (ложно). Для двух аргументов существуют 16 логических функций (операций, логических действий). Полная система этих функций(z0 – z15) для двух аргументов(x,y) показана в таблице. Над переменными в основном производятся три логических действия: сложение, умножение, отрицание (инверсия), что соответствует функциям ИЛИ, И, НЕ. Все функции в булевой алгебре могут быть описаны с помощью таблицы истинности. В нижеследующих таблицах описаны функции И(z₁), ИЛИ(z₇),НЕ(z₁₂).

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания.

Высказывания строятся над множеством {B, , , , 0, 1}, где B — непустое множество, над элементами которого определены три операции:

 отрицание (унарная операция),

 конъюнкция (бинарная),

 дизъюнкция (бинарная),

а логический ноль 0 и логическая единица 1 — константы.

Так же используются названия

• Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например ).

• Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например ).

Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом () либо в виде черты над операндом (), что компактнее, но в целом менее заметно.

Аксиомы:

1. , инволютивность отрицания, закон снятия двойного отрицания

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

Свойства логических операций

Коммутативность: xy = yx, {&, }.

1. Идемпотентность: xx = x, {&, }.

2. Ассоциативность: (xy)z = x(yz), {&, }.

3. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:

• ,

• ,

• .

4. Законы де Мо́ргана:

• ,

• .

Законы поглощения:

• ,

• .

Другие (1):

• .

• .

• .

• .

• , инволютивность отрицания, закон снятия двойного отрицания.

Другие (2):

• .

• .

• .

• .

Другие (3) (Дополнение законов де Мо́ргана):

• .

• .

Теоремы:

В алгебре логики используется целый ряд теорем.

Теоремы для одной переменной:

A \/ 0 = A           4. A \/ Ā = 1         7. A · A = A

2. A \/ 1 = 1           5. A · 0 = 0         8. A · Ā = 0

3. A \/ A = A           6. A · 1 = 1         9. 

Теоремы для двух и более переменных:

10. а) A \/ B = B \/ A,         б) AB = BA

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

11. а) A \/ B \/ C = A \/ (B \/ C) = (A \/ B) \/ C,

б) ABC = A(BC) = (AB)C – сочетательный закон.

12. а) A (B \/ C) = AB \/ AC, б) A \/ BC = (A \/ B)(A \/ C) – распределительный закон.

Данная теорема и все последующие вытекают из принципа двойственности. Применим его к выражению 12, а:

– левая часть,

– правая часть.

Введя новые обозначения: , получим обозначения: , а это и есть теорема 12, б.

13. а) A \/ AB = A, б) A(A \/ B) = A

– закон поглощения (A поглощает B).

Доказательство 13, а:

A \/ AB = A(1 \/ B) = A · 1 = A, (используя теоремы 2, 6).

Теорема 13, б следует из принципа двойственности.

14. а) , б) .

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

, (используя теоремы 8 и 1).

Теорема 14, б следует из принципа двойственности.

15. а) AB \/ ĀB = B, į) (A \/ B)(Ā \/ B) = B, закон склеивания (склеивание по A).

Доказательство 15, а:

AB \/ ĀB = B(A \/ Ā) = B · 1 = B, (используя теоремы 4 и 6).

Теорема 15, б следует из принципа двойственности.