Основные понятия

Элементы теории множеств

A⊂B⇔x∈A⇒x∈BA \sub B \Leftrightarrow x \in A \Rightarrow x \in Bx∈A∪B⇔x∈A∨x∈Bx \in A \cup B \Leftrightarrow x \in A \vee x \in Bx∈A∩B⇔x∈A∧x∈Bx \in A \cap B \Leftrightarrow x \in A \wedge x \in Bx∈A⊂A⇔x∈E∧x∉Ax \in A \subset A \Leftrightarrow x \in E \wedge x \notin AX⊂A∖B⇔x∈a∧x∉BX \subset A \setminus B \Leftrightarrow x \in a \wedge x \notin B

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

Пусть EE — некоторое множество и A,B,CA, B, C — его подмножество.

A∪B=B∪A, A∩B=B∩AA \cup B = B \cup A, ~A \cap B = B \cap AA∪(B∪C)=(A∪B)∪C, A∩(B∩C)=(A∩B)∩CA \cup (B \cup C) = (A \cup B) \cup C, ~A \cap (B \cap C) = (A \cap B) \cap CA∪(B∩C)=(A∪B)∩(A∪C), A∩(B∪C)=(A∩B)∪(A∩C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C), ~A \cap (B \cup C) = (A \cap B) \cup (A \cap C)A∪A=A, A∩A=AA \cup A = A, ~A \cap A = AA∪E=E, A∩E=AA\cup E = E, ~A \cap E = AA∪∅=A, A∩∅=∅A \cup \emptyset = A, ~A \cap \emptyset = \emptysetA∪⊂A=E, A∩⊂A=∅A \cup \subset A = E, ~A \cap \subset A = \emptyset

Элементы математической логики

Предложение в формальной логике о котором можно сказать истино оно или ложно называется высказыванием. Если A∨BA \vee B — некоторое высказывание, то ¬A, A∩B, A∪B,A⇒B, A⇔B\neg A, ~A \cap B, ~A \cup B, A \Rightarrow B, ~A\Leftrightarrow B тоже являются высказываниями.

Таблица истиности

¬A\neg A
AA10
¬A\neg A01
A∧BA \wedge B
A\BA\backslash B10
110
000
A∨BA \vee B
A\BA \backslash B10
111
010
A⇒BA \Rightarrow B
A\BA \backslash B01
110
011
A⇔BA \Leftrightarrow B
A\BA \backslash B10
110
001

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

TT — некоторое истиное высказывание, FF — некоторое ложное высказывание.

A∧T=A, A∨T=TA \wedge T = A, ~A \vee T = TA∧¬A=F, A∪¬A=TA \wedge \neg A = F, ~A \cup \neg A = T¬(A∧B)=¬A∨¬B, ¬(A∨B)=¬A∩¬B\neg (A \wedge B) = \neg A \vee \neg B, ~\neg (A \vee B) = \neg A \cap \neg B

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

Значение истиности логической формулы определяется логическими значениями входящих в неё высказываний. Установить истиность логической формулы можно с помощью таблицы истиности или с помощью равносильных преобразований.

¬A∩B⇒A∪¬B\neg A \cap B \Rightarrow A \cup \neg B
AABB¬A\neg A¬B\neg B¬A∩B\neg A \cap BA∪¬BA \cup \neg BFF
1100011
1001011
0110100
0011011

Формула выполнима при A=(1,1,0), B=(1,0,0).A=(1, 1, 0), ~B=(1, 0, 0).

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

A≡BA \equiv B

Равносильности

Основные равносильности

A∧A≡A, A∨A≡AA \wedge A \equiv A, ~A \vee A \equiv AA∧1≡A, A∨1≡1A \wedge 1 \equiv A, ~A \vee 1 \equiv 1A∧0≡0, A∨0≡AA \wedge 0 \equiv 0, ~A \vee 0 \equiv AA∧¬A≡0, A∨¬A=1A \wedge \neg A \equiv 0, ~A \vee \neg A = 1x∧(y∨x)≡x, x∨(y∧x)≡xx \wedge (y \vee x) \equiv x, ~x \vee (y \wedge x) \equiv x

Равносильности при раскрытии логических операций

A⇔B≡(A⇒B)∩(B⇒A)A \Leftrightarrow B \equiv (A \Rightarrow B) \cap (B \Rightarrow A)A⇒B≡¬A∨BA \Rightarrow B \equiv \neg A \vee B¬(A∨B)≡¬A∧¬B\neg(A \vee B) \equiv \neg A \wedge \neg B

Алгоритм доказательства равносильности логических формул

  1. Из формулы удаляются все операции-стрелки.

  2. Раскрываются все скобки перед которыми знак отрицания.

  3. Используем основные свойства логических операций и основные равносильности первого типа. Порядок раскрытия скобок по приоритетностям.

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

(x⇒y)⇒x(x \Rightarrow y) \Rightarrow x

Логическая формула принимающая значение ноль при любых значениях входящих в неё элементарных высказываний называется тождественно ложной.

Построение отрицания к логической формуле

  1. Все входящии в нее элементарные высказывания меняются их отрицаниями.

    A→¬AA \to \neg A

  2. Все кванторы меняются на смежные.

    ∀→E, E→∀\forall \to E, ~E \to \forall

  3. Все "и" меняются на "или".

    ∧→∨, ∨→∧\wedge \to \vee, ~\vee \to \wedge