7) Основные законы алгебры Буля.

Законов много, основные из них:

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

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

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

8) Понятие интерпретации. Примеры.

9) Понятие исчисления. Понятие формулы исчисления высказываний.

Исчисление высказываний – это аксиоматическая логическая система, интерпретацией которой является алгебра высказываний. Алфавит исчисления высказываний состоит из символов трех категорий:

1. Символы первой категории: Эти символы будем называть переменными высказываниями.

2. Символы второй категории: они носят общее название логических связок.

3. Третью категорию составляет пара символов ( ), называемая скобками.

Других символов исчисление высказываний не имеет.

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

Определение формулы исчисления высказываний.

1. Всякая переменная является формулой.

2. Если А и В- формулы , то слова - тоже формулы.

Никакая другая строчка символов не является формулой

10)Определение доказуемой(выводимой) формулы. Таблица истинности.

Сначала определяются исходные доказуемые выводимые формулы (аксиомы), а затем определяются правила вывода, которые позволяют из имеющихся доказуемых формул получить новые доказуемые формулы.

Образование доказуемой формулы из исходных доказуемых формул путем применения правил вывода называется выводом (доказательством) данной формулы из аксиом.

Таблица истинности — это таблица, описывающая логическую функцию.

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

11)Дерево редукции.

12) Понятие о выводимости формулы из совокупности формул. Понятие вывода.

если A и A →B — выводимые формулы, то B — также выводимая формула.

Выводом из конечной совокупности формул Н называется всякая конечная последовательность формул В₁,В₂,…,В_к, всякий член которой удовлетворяет одному из следующих трех условий:

1)он является одной из формул совокупности Н,

2)он является доказуемой формулой,

3)он получается по правилу заключения из двух любых предшествующих членов последовательности В₁,В₂,…,В_к.

13) Формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний. Для этого будем трактовать переменные исчисления высказываний как переменные алгебры высказываний, т. е. переменные в содержательном смысле, принимающие два значения: истина и ложь (1 и 0).

Операции определим так же, как в алгебре высказываний.

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

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

Каждая тождественно истинная формула алгебры высказываний доказуема в исчислении высказываний