Минимизация формул алгебры высказываний

Представление логической формулы высказываний в виде таблицы истинности.

Основные логические операции и соответствующие им таблицы истинности

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

Определение 1. Объединение двух или нескольких высказываний в одно с помощью союза И называется операцией логического умножения или конъюнкцией. Возможны различные варианты записи конъюнкции:

Для упрощения знак конъюнкции опускается и записывается следующим образом: Истинность логического произведения устанавливается с помощью таблицы 2.3.1:

Таблица 2.3.1.

А	В	АÙВ

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

Определение 2. Объединение двух или нескольких высказываний в одно с помощью союза ИЛИ, употребляемого в не исключающем смысле, называется операцией логического сложения, или дизъюнкцией. Она может быть записана в одном из двух видов:

Например:

Если А: Спортсмены находятся в спортзале,

В: Спортсмены играют в баскетбол,

то Спортсмены находятся в спортзале или спортсмены играют в баскетбол.

Таблица истинности для суммы высказываний имеет вид:

Таблица 2.3.2.

А	В	АÚВ

Таким образом, сумма истинна только тогда, когда истинно хотя бы одно из слагаемых.

Определение 3. Присоединение союза НЕ к некоторому высказыванию называется операцией отрицания. Например, если А - "Идет дождь", то отрицанием А () является высказывание "Дождь не идет". Суть операции формализуется с помощью таблицы 2.3.3.

Таблица 2.3.3.

А

Определение 4. Соединениевысказываний союзом тогда и только тогда, когда определяет операцию эквиваленции или двойной импликацией и обозначается знаком «или ~. Этой операции соответствует таблица 2.3.4:

Таблица 2.3.4.

А	В	А~В

Высказывание A«B истинно тогда и только тогда, когда значения А и В совпадают.

Например:

высказывания "24 делится на 6 тогда и только тогда, когда 24 делится на 3", "23 делится на 6 тогда и только тогда, когда 23 делится на 3" истинны,

а высказывания "24 делится на 6 тогда и только тогда, когда 24 делится на 5", "21 делится на 6 тогда и только тогда, когда 21 делится на 3" ложны.

Определение 5. Операция при помощи, которой высказывания объединяются связкой "если..., то" называют импликацией и обозначают знаком ®. Высказывание A®B ложно тогда и только тогда, когда А истинно, а В ложно.

Таблица 2.3.5.

А	В	А®В

Импликацию можно выразить через дизъюнкцию и отрицание:

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

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

Предположим, что задано сложное высказывание например, . Необходимо установить истинность этого высказывания с помощью таблицы истинности. В соответствии приведенным выше правилом построим следующую таблицу 2.3.6.

Таблица 2.3.6

	A	B	C		F

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

…………………..;

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

Таким образом,

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

Таблица 2.3.7

	A	B	AÚB	BÚA

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

Примеры тождественно истинных формул:

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

Тождественно истинные и тождественно ложные высказывания заменяются в формулах соответственно 1 или 0, например:

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

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

Дата добавления: 2014-10-17