Вопросы_по_мат_логике_3_сем_экз_Дьячков / Dokument

11) Исчисление высказываний

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

Описание всякого исчисления включает в себя описание символов этого исчисления (алфавита); формул, являющихся конечными конфигурациями символов и определение выводимых формул.

Алфавит исчисления высказываний состоит из символов трех категорий:

1) Символы первой категории: x, y, z,…,x₁, x₂,…, которые называются переменными высказывания;

2) Символы второй категории: , которые называются логическими связками. – дизъюнкция (логическое сложение), – конъюнкция (логическое умножение), → – импликация (логическое следование), ¯ – отрицание;

3) Символы третьей категории: скобки.

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

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

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

1. Всякая переменная x, y, z,… является формулой.

2. Если A и B – формулы, то слова – формулы.

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

Переменные высказывания называются элементарными формулами.

Определение подформулы.

1. Подформулой элементарной формулы является только она сама.

2. Если формула имеет вид , то ее подформулами являются: она сама, формула и все подформулы формулы .

3. Если формула имеет вид (под символом понимается любая из трех связок ), то ее подформулами являются: она сама, формулы и , все подформулы формул и .

Замечание. Скобки в записи формул можно опускать по тем же правилам, что и в алгебре высказываний.

Система аксиом исчисления высказываний:

I группа. I₁ x→(y→x); I₂ (x→(y→z))→((x→y)→(x→z)).

II группа. II₁ ; II₂ ; II₃ .

III группа. III₁ ; III₂ ; III₃ .

IV группа. IV₁ ; IV₂ ; IV₃ .

12) Терм — выражение формального языка (системы) специального вида. Понятие терма определяется индуктивно:

1. всякая свободная переменная есть терм;

2. всякая индивидная константа есть терм;

Предика́т (n-местный, или n-арный) — это функция с множеством значений.Таким образом, каждый набор элементов множества M характеризуется либо как «истинный», либо как «ложный».

Предикат можно связать с математическим отношением: если (m1,m2,…,mn) принадлежит отношению, то предикат будет возвращать на ней 1. В частности, одноместный предикат определяет отношение принадлежности некоторому множеству.

Предикат — один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам.

если на любом наборе аргументов он принимает значение 1.

если на любом наборе аргументов он принимает значение 0.

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

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

Ква́нтор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание. Чаще всего упоминают:

• Квантор всеобщности читается: «для любого…», «для каждого…», «для всех…» или «каждый…», «любой…», «все…»).

• Квантор существования (, читается: «существует…» или «найдётся…»).

В математической логике приписывание квантора к формуле называется связыванием или квантификацией

Превратить предикат в высказывание можно, поставив перед предикатом слова («все», «существует» и другие), называемые в логике кванторами.