2015-06-05
611
Алгебра высказываний – раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Алгебра высказываний возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Буль первым показал, что существует аналогия между алгебраическими и логическими действиями, так как и те, и другие предполагают лишь два варианта ответов – истина или ложь, нуль или единица.
Высказывание – это повествовательное предложение, про которое можно утверждать однозначно истинно оно или ложно. На основе анализа логической связи между высказываниями делается логический вывод. Для получения логического вывода составляется таблица истинности, в которой записывают все возможные комбинации каждого простого высказывания.
Работа ЭВМ как автоматических устройств основана исключительно на математически строгих правилах выполнения команд, программ и интерпретации данных. Тем самым работа компьютеров допускает строгую однозначную проверку правильности своей работы в плане заложенных в них процедур и алгоритмов обработки информации. Это позволяет использовать математический аппарат для анализа и разработки логических устройств вычислительной техники. Функцией логических переменных (булевой функцией) называют взаимосвязь логических переменных по законам логики. Значения входных переменных и выходных функций связаны некоторым преобразованием, которое реализует логическую функцию.
|
|
|
Определим основные логические действия.
Инверсия (логическое отрицание)
Операция, выражаемая словом "не", называется логическим отрицанием (инверсией,) делает истинное высказывание ложным и, наоборот, ложное – истинным. Обозначается 
.Таблица истинности для логического выражения А имеет вид
| А |
|
Конъюнкция (логическое умножение)
Операция, выражаемая связкой "и", называется логическим умножением (конъюнкцией) и обозначается знаком 
(может обозначаться знаком & или точкой). Высказывание А В истинно тогда и только тогда, когда оба высказывания А и В истинны. Таблица истинности для логических переменных A и B
| А | В | А /\ B |
Дизъюнкция (логическое сложение) Операция, выражаемая связкой "или" (в неисключающем смысле этого слова), называется логическим сложением (дизъюнкцией) и обозначается знаком 
(или +). Высказывание А В ложно тогда и только тогда, когда оба высказывания А и В ложны. Таблица истинности для логических переменных A и B
| А | В | А B
|
Импликация (следование) Операция, выражаемая связкой "если …, то …", называется импликацией и обозначается знаком 
(или 
). Высказывание А В ложно тогда и только тогда, когда А =1 и В=0. Таблица истинности для логических переменных A и B
|
|
|
| А | В | А B
|
Эквиваленция Операция, выражаемая связкой " …тогда и только тогда, когда …", называется эквиваленцией и обозначается знаком 
(или 
). Высказывание А В истинно тогда и только тогда, когда значения А и В совпадают. Таблица истинности для логических переменных A и B
| А | В | А B
|
В алгебре логики любую логическую функцию можно выразить через основные логические операции, записать ее в виде логического выражения и упростить ее, применяя законы логики и свойства логических операций. По формуле логической функции легко рассчитать ее таблицу истинности. Необходимо только учитывать порядок выполнения логических операций (приоритет) и скобки. Операции в логическом выражении выполняются слева направо с учетом скобок.
Приоритет выполнения логических операций:
- инверсия,
- конъюнкция,
- дизъюнкция.
Виды формул алгебры высказываний
Тавтология или тождественно-истинная формула – при всех наборах значений переменных равна 1.
Противоречие или тождественно-ложная формула – при всех наборах значений переменных равна 0.
Выполнимая или опровержимая – при некоторых наборах значений переменных равна 1, при других равна 0.
3 Практическая часть
Задача 3.1 Построить таблицу истинности для логического высказывания 
. Определите вид формулы.
Решение. Определить количество строк в таблице истинности, которое равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение: количество строк равно 
, где n – количество переменных. Количество логических переменных – 2 (A, B) поэтому количество строк равно 
= 4. Заполним таблицу истинности, выполняя действия в правильном порядке. Для этого расставим скобки 
. Составим таблицу истинности:
| A | B |
| 
|
|
Формула является выполнимой или опровержимой, так как при некоторых наборах значений переменных равна 1, при других равна 0.
Задача 3.2 Построить таблицу истинности для логического высказывания 
Решение. Определить количество строк в таблице истинности, которое равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение: количество строк равно , где n – количество переменных. Количество логических переменных – 3 (A, B,С) поэтому количество строк равно 
= 8. Заполним таблицу истинности, выполняя действия в правильном порядке, для этого расставим скобки 
. Составим таблицу истинности:
| A | B | С | 
| 
| 
|
|
