Что называется формулой логики высказываний кратко

Обновлено: 02.07.2024

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

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

Для построения формул логики высказываний кроме символов (1) используются знаки логических операций

а также символы, обеспечивающие возможность однозначного прочтения формул, — левая и правая скобки:

Понятие формулы логики высказываний определим следующим образом:

1) элементарные формулы (атомы) суть формулы логики высказываний;

2) если А и В — формулы, то тоже являются формулами логики высказываний;

3) только те выражения являются формулами логики высказываний, для которых это следует из 1) и 2).

Определение формулы содержит перечисление правил образования формул. Согласно определению, всякая формула логики высказываний либо есть атом, либо образуется из атомов в результате последовательного применения правила 2). Например, выражения

являются формулами логики высказываний.

Обозначать произвольные формулы логики высказываний будем большими буквами латинского алфавита (возможно, с индексами):

При этом не исключено, что одна и та же формула может быть обозначена различными буквами.

Заметим, что никакой атом не имеет вида Такой вид имеют сложные формулы.

Пример. В формуле скобки восстанавливаются следующими шагами:

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

Логика высказываний (или пропозициональная логика от англ. propositional logic , или исчисление высказываний [1] ) — это формальная теория, основным объектом которой служит понятие логического высказывания. С точки зрения выразительности, её можно охарактеризовать как классическую логику нулевого порядка.

Несмотря на свою важность и широкую сферу применения, логика высказываний является простейшей логикой и имеет очень ограниченные средства для исследования суждений [1] .

Содержание

Основные понятия

Базовыми понятиями логики высказываний являются пропозициональная переменная — переменная, значением которой может быть логическое высказывание, и (пропозициональная) формула, определяемой индуктивно следующим образом [2] :

Множество пропозиционных формул называется языком логики высказываний (англ. propositional language , PL) [2] .

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

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

Элементарное высказывание (буква) является формулой нулевого уровня. Если элементарное логическое высказывание всегда верно, мы будем его обозначать буквой И, а если оно всегда неверно, — буквой Л. Тогда формулы первого уровня — это элементарные высказывания, к которым применена только одна логическая связка.
Пусть Ф1 и Ф2 — формулы ненулевого уровня. Тогда записи (¬(Ф1)), ((Ф1)(Ф2)), ((Ф1)(Ф2)), ((Ф1)→(Ф2)) также являются формулами. Если же одна из формул Ф1 и Ф2 , к которым применяется логическая связка, имеет нулевой уровень, то она в скобки не заключается.

Теперь, зная буквы-элементарные высказывания, мы никогда не ошибёмся, определяя, является ли формулой запись, содержащая эти буквы, скобки и символы связок, то есть правильно ли построено сложное высказывание. В процессе подобного опознавания мы выделяем части формулы, то есть более короткие формулы, из которых на каждом этапе строится более длинная формула с применением одной связки. Самыми простыми частями формулы являются, разумеется, элементарные высказывания. Значит, логический анализ формулы сводится к выделению всех её частей.

Пример

Пусть элементарными высказываниями являются А, В, С. Записи

¬ A BC и (B)(BA→C)

c формальной точки зрения не являются формулами, так как мы натыкаемся при их разборе на нарушение правил построения формул. (В первом случае отсутствует логическая связка между B и C и отсутствуют скобки вокруг ¬A. Во втором случае формула нулевого уровня В включена в скобки). А записи

(¬ A)(BC) и B((BA)→C)

вполне соответствуют требованиям построения формулы. В процессе анализа формулы (¬ A)(BC) выделяются следующие её части:

Соглашения о скобках

Поскольку в построенных по определению формулах оказывается слишком много скобок, иногда и не обязательных для однозначного понимания формулы, математики приняли соглашения о скобках, по которым некоторые из скобок можно опускать. Записи с опущенными скобками восстанавливаются так:

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

Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.

Например: запись означает формулу , а её длина равна 12.

Истинностное значение

Интерпретацией (моделью) языка логики высказываний называется функция из множества всех пропозициональных переменных в множество истинностных значений . Основной задачей логики высказываний является установление истинностного значения формулы, если даны истинностные значения входящих в неё переменных. Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок [3] .

$\neg p$

Оценка отрицания задаётся таблицей:

$p\!$	$\neg p$
$0\!$	$1\!$
$1\!$	$0\!$

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

$p\!$	$q\!$	$p\rightarrow q$	$p \wedge q$	$p \vee q$

Тождественно истинные формулы (тавтологии)

Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных (то есть, при любой интерпретации) [4] . Вот несколько широко известных примеров тождественно истинных формул логики высказываний:

$\neg (p \vee q) \leftrightarrow (\neg p \wedge \neg q)$

1) ;

$\neg (p \wedge q) \leftrightarrow (\neg p \vee \neg q)$

2) ;

$(p\rightarrow q)\leftrightarrow(\neg q\rightarrow \neg p)$

;

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

$p\vee(p\wedge q)\leftrightarrow p$

1) ;

$p\wedge(p\vee q)\leftrightarrow p$

2) ;

$p\wedge(q\vee r)\leftrightarrow(p\wedge q)\vee(p \wedge r)$

1) ;

$p\vee(q\wedge r)\leftrightarrow(p\vee q)\wedge(p \vee r)$

2) .

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

Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:

$A_1 : A \rightarrow (B \rightarrow A)$

;

$A_2 : ((A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C)))$

;

$A_3 : A \wedge B \rightarrow A$

;

$A_4 : A \wedge B \rightarrow B$

;

$A_5 : A \rightarrow (B \rightarrow (A \wedge B))$

;

$A_6 : A \rightarrow (A \vee B)$

;

$A_7 : B \rightarrow (A \vee B)$

;

$A_8 : (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C))$

;

$A_9 : \neg A \rightarrow (A \rightarrow B)$

;

$A_<10> : (A \rightarrow B) \rightarrow ((A \rightarrow \neg B)\rightarrow \neg A)$
;

$A_<11> : A\vee\neg A$
.

вместе с единственным правилом:

$\frac<A \rightarrow B, A> $
(Modus ponens)

Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

Свидетельство и скидка на обучение каждому участнику

Зарегистрироваться 15–17 марта 2022 г.

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

Формулами логики высказываний называются составные высказывания, построенные из простых высказываний с помощью логических связок. Формулы состоят из:

- знаков логических операций: Ø , &, Ú , ® , « , Å

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

- любая переменная, обозначающая высказывание, является формулой ;

- других формул нет.

Порядок выполнения логических операций в сложном логическом выражении:

Л ишние скобки опускаются.

Порядок построения формул логики высказываний на основе сложных высказываний:

1. Разложить сложное высказывание на простые высказывания.

2. Каждому простому высказыванию назначить соответствующую логическую переменную.

3. Определить логические операции над простыми высказываниями.

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

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

Л огическая формула примет вид:

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

Сложное высказывание включает два простых высказывания:

Далее объединим представленные выше два высказывания в одно связкой &:

Составное высказывание состоит из следующих простых высказываний:

Логическая формула второго составного высказывания:

Первое составное высказывание состоит из следующих простых высказываний:

С учетом введенных обозначений и определенных логических связок сложное высказывание будет представлено в виде следующей логической формулы:

Первое предложение содержит следующие простые высказывания:

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

Второе предложение содержит другие простые высказывания:

Логическая формула, представляющая второе предложение:

В третьем предложении содержатся новые простые высказывания:

Логическая формула для третьего предложения:

Окончательно составное высказывание записывается следующей логической формулой:

((А&В) ® (С ↔ D ))&((К& L ) ® (С ↔ D ))&((К&М) ® N ).

Упражнения для самостоятельной работы.

Представить логическими формулами следующие высказывания:

Элементарные высказывания в логике высказывания рассматриваются как не расчленяемые "атомы", а составные высказывания - как "молекулы'', образованные из "атомов" применением к ним логических операций. Логика высказываний интересуется единственным свойством элементарных высказываний их значением истинности, составные же высказывания изучаются ею со стороны их структуры, отражающей способ, которым они образованы. Структура составных высказываний определяет зависимость их значений истинности от значений истинности составляющих элементарных высказываний.

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

Например, высказывание: "Если 20 делится на 2 и на 5, то 20 делится на 10", формализуется в виде . Такая же формула соответствует предложению: "если в четырехугольнике две противоположные стороны равны и параллельны, то этот четырехугольник - параллелограмм "

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

1) А,В,С и т.д. - символы для обозначения высказываний;

3) - символы, логические операции;

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

Дадим строгое определение формулы логики высказываний.

1) Всякое высказывание – это формула;

2) Символы 1, 0 – формулы;

3) Если А - формула, то - тоже формула;

4) Если А₁ и А₂ - формулы, то

5) - формулы;

6) Никаких других формул в логике высказываний нет.

Алгоритм формализации высказывания

1) Простые высказывания заменяем переменными;

2) Логические связки заменяем соответствующими символами;

3) Расставляем вспомогательные символы, скобки: ( , ) в соответствии со смыслом данного высказывания.

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

Истинность или ложность высказывания мы будем задавать таблицей истинности.

Составление истинностных таблиц происходит по следующему правилу:

Сначала необходимо записать всевозможные наборы высказываний, при этом каждое из высказываний может войти в одном из двух состояний (0 или 1). Далее, последовательно, в соответствии с порядком выполнения логических операций, под каждой логической операцией следует записывать истинные значения. Обратите внимание, если формула содержит п высказываний, то таблица истинности будет содержать строк.

При составлении таблиц необходимо следить за тем, чтобы не перепутать порядок действий. Заполняя таблицу, следует двигаться "изнутри наружу", то есть от элементарных формул к более и более сложным. Столбец, заполняемый последним, содержит значения исходной формулы /4/.

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

А	В
0	0	1	1	0	0
0	1	1	1	1	1
1	0	0	0	0	1
1	1	0	1	0	0

Пример 2: Вычислить значение функции:

при

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

Две формулы А и В будем называть равносильными (А=В или ), если они имеют одинаковые таблицы истинности. Будем считать две таблицы истинности одинаковыми, если у них одинаковые последние (результирующие) столбцы.

x	y
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

В логике высказываний будем считать, что равносильные формулы задают одно и то же высказывание. Может оказаться, что в последнем столбце таблицы истинности стоят одни единицы или нули. Будем называть такое высказывание тождественно-истинным (тавтологией) соответственно тождественно-ложным (противоречием) и обозначать 1 и 0. Из определения следует, что для проверки равносильности формул нужно построить их таблицы истинности и сравнить