Формулы алгебры логики Понятие высказывания. Основные логические операции. Формулы логики. Таблица истинности и методика её построения.

Высказыванием называется утверждение, которое является истинным или ложным Москва – столица России истинное высказывание 5 – четное число ложное высказывание не высказывание Студент второго курса не высказывание Который час? не высказывание

Обозначение - Функция истинности

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

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

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

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

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

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

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

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

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

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

Пример

Формула алгебры логики отдельно стоящая буква A, B, C,..., X, Y, Z... – формула если А, В - формулы, то формулами являются и А, В, А В, А В, АВ, АВ, А I В, А В, А В. других формул нет

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

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

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

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

Решить самостоятельно

Ответы 1

2

3

4