Также по теме

АЛГЕБРА ВЫСКАЗЫВАНИЙ

АЛГЕБРА ВЫСКАЗЫВАНИЙ является составной частью одного из современных быстро развивающихся разделов математики – математической логики. Математическая логика применяется в информатике, позволяет моделировать простейшие мыслительные процессы. Одним из занимательных приложений алгебры высказываний – решение логических задач.

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

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

Объектами алгебры высказываний являются высказывания. Высказывание – это истинное или ложное повествовательное предложение. Повествовательное предложение, в котором говорится об одном-единственном событии, называется простым высказыванием. Например, предложение «Луна – спутник Земли» есть простое высказывание, предложение «Не сорить!» не является высказыванием.

Высказывания обозначаются большими буквами латинского алфавита. Если высказывание A истинно, то пишут A = 1, если ложно, то используют запись A = 0.

Как и в других алгебрах, в алгебре высказываний над ее объектами (высказываниями) определены действия, выполняя которые получают новые высказывания. Объединение двух высказываний в одно при помощи союза «И» называется операцией логического умножения. Полученное таким образом высказывание называется логическим произведением. Например, высказывание A – «В лесу растут грибы», высказывание B – «Льюис Кэрролл – математик», составим произведение этих высказываний AB – «В лесу растут грибы и Льюис Кэрролл – математик». Истинность произведения высказываний зависит от истинности перемножаемых высказываний и может быть определена с помощью следующей таблицы:

Таблица 1
А В АВ
1 1 1
1 0 0
0 1 0
0 0 0

Объединение двух высказываний в одно с помощью союза «ИЛИ», употребляемого в неисключающем смысле, называется операцией логического сложения. Например, высказывание A – «Декабрь – зимний месяц», В – «Летом иногда идет дождь», определим высказывание A+B – «Декабрь – зимний месяц или летом иногда идет дождь». Установить истинность логической суммы можно с помощью следующей таблицы:

Таблица 2
А В А+В
1 1 1
1 0 1
0 1 1
0 0 0

Операция логического отрицания осуществляется над одним высказыванием. Выполнить операцию логического отрицания (обозначается ) – значит получить из данного высказывания новое, присоединяя слова «неверно, что …» ко всему высказыванию. Истинность высказывания определяется таблицей:

Таблица 3
А
1 0
0 1

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

Таблица 4
А B A
1 1 0 0 1
1 0 1 1 0
0 1 0 0 1
0 0 1 0 1

Тождественные высказывания. Эквивалентные высказывания. Формулы Августа де Моргана.

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

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

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

, .