Формулы логики

Формальная логика изучает только истинность и ложность высказываний.
Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.
Результат выполнения логической операции можно представить как истинность (1) или ложность (0) некоторого высказывания.

Высказыванием называется утверждение, которое является истинным или ложным

Основные логические операции
Дизъюнкция – переход к составному высказыванию, которое является истинным, если истинно хотя бы одно из высказываний А и В
Обозначение A∨B
Лексический аналог - «или», «либо», ...
Функция истинности

Основные логические операции
Конъюнкция – переход к составному высказыванию, которое является ложным, если ложно хотя бы одно из высказываний А и В
Обозначение A&B,
Лексический аналог - «и», «а», ...
Функция истинности

Основные логические операции
Отрицание (инверсия) – переход к новому высказыванию, которое является истинным, если высказывание А ложно и ложно в противном случае.
Обозначение
Лексический аналог - «не»
Функция истинности

Основные логические операции
Импликация – переход к составному высказыванию, которое является ложным, если из истинного высказывания следует ложное.
Обозначение
Лексический аналог - «если..., то...»
Функция истинности

Основные логические операции
Эквиваленция – переход к составному высказыванию, которое является ложным, если посылки имеют противоположные логические значения.
Обозначение
Лексический аналог - «тогда и только тогда, когда...»
Функция истинности

Другие логические операции
Кольцевая сумма, сумма Жегалкина, сумма по модулю 2, двоичное сложение – антиэквиваленция
Обозначение
Лексический аналог – «либо…, либо…»
Кольцевая сумма истинна в том и только в том случае, когда исходные высказывания A и B не равны между собой.
Функция истинности

Другие логические операции
Стрелка Пирса – антидизъюнкция
Обозначение
Лексический аналог – «ни…, ни…»
Стрелка Пирса истинна в том и только в том случает, когда оба высказывания A и B ложны
Функция истинности

Другие логические операции
Штрих Шеффера – антиконъюнкция
Обозначение
Лексический аналог – «не… или не…»
Штрих Шеффера ложный в том и только в том случае, когда оба высказывания A и B истинны
Функция истинности

Приоритет операций
Выполняются действия в скобках
Внешние скобки не пишутся
Остальные операции выполняются согласно схеме

Пример
2
3
4
1
5
6
1
2
3
4
5
6

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

Построение таблицы истинности
Подсчитать количество переменных в формуле n.
Определить количество строк в таблице –
Подсчитать количество операций в формуле и определить количество столбцов m + n.
Записать названия столбцов с учетом последовательности выполнения операций.
Заполнить столбцы переменных наборами от 00...0 до 11...1 в лексикографическом порядке, используя метод «последовательного деления столбцов пополам»
Заполнить таблицу по столбцам.

Примеры
n=3
m=6

Примеры
n=3
m=6