Бинарные связки

Унарная связка

Логические связки.

Формулы логики высказываний

Элементарные высказывания принимают одно из двух значений {0,1}.

Пропозициональными переменными (обозначаются маленькими буквами) называются переменные, значениями которых являются элементарные высказывания.

х	Øх

Отрицание: ØА (читается: не-А)

Смысл отрицания определяется таблицей.

Конъюнкция: (читается А и В)

Дизъюнкция: (А или В)

Импликация: (из А следует В)

Результат импликации ложен только тогда, когда исходное (А) высказывание ложно, а результат (B) истинен.

Пояснение: (x делится на 4) -> (x делится на 2) – истина при любом х.

Поэтому (5 делится на 4) -> (5 делится на 2) и (2 делится на 4) -> (2 делится на 2) должны быть истинами.

Эквивалентность: , , А=В (А равносильно В)

Результат эквивалентности есть истина, если A и B одновременно истинны, либо одновременно ложны (иными словами, если A=B).

Сложение по модулю 2: АÅВ (либо А, либо В)

Смысл этих связок определяется таблицей:

x1	x2	х1&х2	х1Vх2	х1->х2	х1=х2	х1Åх2

ОПРЕДЕЛЕНИЕ. Пропозициональной формулой называется строка символов, которая является либо пропозициональной переменной, либо совпадает с одной из строк (ØА), , (, (, (, (АÅВ), где A и B – формулы.

Для сокращения числа скобок в формуле принято опускать скобки, не влияющие на результат. Соглашение о порядке выполнения (приоритете, силе связывания) операций, позволяет отбросить скобки, связывающие разные операции. Порядок выполнения логических операций следующий: сначала выполняются операции в скобках, затем операции отрицания, далее - конъюнкция, дизъюнкция, импликация, эквивалентность, сложение по модулю 2.

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

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

Пример. Если x1=1, x2=1, x3=0, то значение формулы равно 0.

Если же ставится задача определить все возможные значения формулы, строится ее таблица истинности. В этой таблице начальные столбцы соответствуют исходным (элементарным) высказываниям, а последний - результирующему (сложному) высказыванию. В начальных столбцах проставляются все возможные комбинации истинности элементарных высказываний, а в последнем истинность сложного высказывания. Каждой комбинации исходных высказываний в формуле соответствует отдельная строка. Число значений формулы (и число строк таблицы) определяется числом элементарных высказываний n и равно 2^n.

Дата добавления: 2015-06-27