Логика высказываний

 

Формула (φ˅ψ), ложна, если и только если ложны все ее дизъюнкты. Во всех остальных случаях она истинна.

Импликацией формул φ и ψ называется формула (φﬤψ), которая ложна тогда, когда истинна φ и ложна ψ, и которая истинна во всех остальных случаях.

Таблица истинности импликации двух произвольных формул  φ и ψ имеет следующий вид

 

Первый аргумент φ	Второй аргумент ψ	Значение функции (φﬤψ)
T	T	T
T	F	F
F	T	Т
F	F	Т

 

В формуле  (φﬤψ) подформулу φ принято называть антецедентом (предшествующий), а подформулу ψ – консеквентом (следствие).

Импликация однозначно истинна в двух случаях: если ее антецедент ложен, или ее консеквент истинен.

Антецедент есть только достаточное условие истинности консеквента, консеквент есть только необходимое условие истинности антецедента.

Эквивалентностью формул φ и ψ называется формула (φ≡ψ), которая истинна тогда, когда формулы φ и ψ обе истинны, или ложны одновременно, и которая ложна во всех остальных случаях.

Таблица истинности эквивалентности  двух произвольных формул  φ и ψ имеет следующий вид

 

Первый аргумент φ	Второй аргумент ψ	Значение функции (φ≡ψ)
T	T	T
T	F	F
F	T	F
F	F	Т

 

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

Сильной дизъюнкцией формул φ и ψ называется формула (φ≠ψ), которая истинна тогда, когда либо формула φ истинна и  формула ψ ложна, либо формула φ ложна и формула ψ  истинна, и которая ложна во всех остальных случаях.

Таблица истинности сильной дизъюнкции двух произвольных формул  φ и ψ имеет следующий вид

 

Первый аргумент φ	Второй аргумент ψ	Значение функции (φ≠ψ)
T	T	F
T	F	Т
F	T	Т
F	F	F

 

Сильная дизъюнкция представляет собой логическое отрицание эквивалентности.

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

 

Второе по значимости в ЛВ – понятие логического союза (связки). С их помощью из простых высказываний образуются сложные.

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

В ЛВ по соглашению допускается, что каждое простое высказывание либо истинно, либо ложно. При этом некоторые сложные (противоречивые) высказывания могут быть одновременно истинными и ложными.

Допущение бивалентности: каждое простое высказывание ЛВ либо истинно, либо ложно.

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

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

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

 

 

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

 

Все формулы ЛВ разделяются на два класса – выполнимые и невыполнимые.

 

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

Выполнимые		Невыполнимые
Логически истинные (тавтологии)	Логически нейтральные (правдоподобные)	Логически ложные (противоречивые)

 

Формула ЛВ считается выполнимой, если существует хотя бы одна интерпретация (набор значений истинности атомарных формул), в которой она истинна, и невыполнимой в противном случае.

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

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

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

 

Логика высказываний как инструмент

 методологического  анализа.

 

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

Истинность любого закона проверяется с помощью таблиц истинности.

Закон снятия двойного отрицания: ¬¬ φ≡ψ. Двойное отрицание не изменяет начального значения истинности высказывания: если оно было истинным (ложным), то в результате двойного отрицания и остается истинным (ложным). Поэтому двойное отрицание всегда может быть снято и заменено обычным утверждением.

Законы  коммутативности (перестановочности) & и ˅:

(φ & ψ) ≡ (ψ & φ)

(φ ˅ ψ) ≡ (ψ ˅ φ)

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

Законы ассоциативности (соединения) & и ˅:

((φ & ψ) & γ) ≡ (ψ & (φ & γ))

((φ ˅ ψ) ˅ γ) ≡ (ψ ˅ (φ ˅ γ))

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

Законы дистрибутивности (распределения) & относительно ˅, и наоборот:

(φ & (ψ ˅  γ)) ≡ ((φ & φ ) ˅ (φ & γ))

(φ ˅ (ψ &  γ)) ≡ ((φ ˅ ψ ) & (φ ˅ γ))

Данные законы позволяют «выносить за скобки» формулы, входящие во все конъюнкты или во все дизъюнкты, а также совершать обратную операцию.

Законы  идемпотентности (сохранения степени):

(φ & φ) ≡ φ

(φ ˅ φ) ≡ φ

Согласно данным законам значение истинности сложных высказываний с многократным вхождением одного и того же конъюнкта (дизъюнкта) полностью определяется значением истинности одного конъюнкта (дизъюнкта).

Законы удаленияﬤ , ≡ и ≠:

(φ ﬤ ψ) ≡ (¬φ ˅ ψ);

(φ = ψ) ≡ ((φ ﬤ ψ) & (φ ﬤ ψ))

 ≡ ((¬φ ˅ ψ) & (φ ˅ ¬ψ))

 ≡ ((φ & ψ) ˅ (¬φ &¬ψ))

(φ ≠ ψ) ≡ ((φ ﬤ¬ ψ) & (¬φ ﬤ ψ))

 ≡ ((¬φ ˅ ¬ψ) & (φ ˅ ψ))

 ≡ ((φ & ¬ψ) ˅ (¬φ & ψ))

Согласно приведенным законам формулы, содержащие логические союзы ﬤ , ≡ и ≠, могут равным образом заменяться на формулы, содержащие только логические союзы ¬,  & и ˅.

Законы де Моргана (отрицания конъюнкции и дизъюнкции):

¬ (φ & ψ) = (¬φ ˅ ¬ψ);

¬ (φ & ψ) = (¬φ ˅ ¬ψ).

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

(φ & (φ ˅ ψ)) ≡ φ;

  (φ ˅ (φ & ψ)) ≡ φ.

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

Законы исключения (противоречащих конъюнктов и дизъюнктов):

((φ & ψ) ˅ (φ &¬ ψ)) ≡ φ;

((φ ˅ ψ) & (φ ˅ ¬ ψ)) ≡ φ.

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

 

Метод деревьев – способ анализа и преобразования формул ЛВ. Его отличает универсальность, простота и эффективность.

Каждая формула логики высказываний может быть представлена не только аналитически, но и графически – в виде дерева, воспроизводящего ее логическую структуру. Каждая ветвь такого дерева указывает условие истинности рассматриваемой формулы, а все вместе они составляют ее объем в традиционном смысле. Графически изобразить структуру какой-либо формулы означает построить ее дерево по общим правилам.

Процесс конструирования дерева формулы завершается одним из следующих возможных результатов:

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