1. Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество: количество подмножеств конечного множества

6. Типы формул.
. Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом.
B случае двух множеств А, B {\displaystyle A,B}формула включений-исключений имеет вид:
[A U B] = [A] + [B] – [A n B]
{\displaystyle |A\cup B|=|A|+|B|-|A\cap B|.}В сумме [A] + [B] {\displaystyle |A|+|B|} элементы пересечения A n B {\displaystyle A\cap B} учтены дважды, и чтобы компенсировать это мы вычитаем [A n B]{\displaystyle |A\cap B|} из правой части формулы. 

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

7. Понятие элементарных конъюнкции и дизъюнкции. Понятие нормальных форм формул.
Элементарная конъюнкция – формула, если она содержит переменные, отрицание переменных и операцию конъюнкции. Элементарная дизъюнкция – формула, если она содержит переменные, отрицание переменных и операцию дизъюнкции. Дизъюнктивно-нормальная форма (ДНФ) – формула, если она является дизъюнкцией элементарных конъюнкций. Конъюнктивно-нормальная форма (КНФ) – формула, если она является конъюнкцией элементарных дизъюнкций. Теорема: для любой формулы А, можно найти формулу В, находящиеся в КНФ или ДНФ, для которой будет справедливо утверждение АΞВ. Формула находится в СДНФ, относительно списка формулы А, если выполняются условия: 1) формула находится в ДНФ; 2) каждый дизъюнктивный член формулы А, является k-членной конъюнкцией, причем на любом месте, этой конъюнкции, находится либо высказывательная переменная, либо ее отрицание; 3)все дизъюнктивные члены А попарно различны. Формула находится в СКНФ, относительно списка формулы А, если выполняются условия: 1) формула находится в КНФ; 2) каждый конъюнктивный член формулы А, является k-членной дизъюнкцией, причем на любом месте, этой дизъюнкции, находится либо высказывательная переменная, либо ее отрицание; 3)все конъюнктивные члены А попарно различны.