Алгебра логики. Понятие высказывания.
Для проектирования, оптимизации и описания компьютерных схем широко используется алгебра логики, которая устанавливает закономерности формирования и преобразования логических функций.
Логика появилась приблизительно в IV веке до нашей эры. Основоположником формальной логики принято считать выдающегося древнегреческого философа Аристотеля. Он систематизировал различные научные сведения, сформулировал формы и правила логического мышления. Труды, посвященные логике, Аристотель описал в цикле философских сочинений, известных под названием «Органон».
Впервые алгебраические методы для решения традиционных логических задач применил основатель математической логики английский математик и логик Джордж Буль. Свои исследования он опубликовал в работах «Математический анализ логики» (1847), «Логическое исчисление» (1848), «Исследование законов мышления» (1854).
Спустя почти 100 лет в 1938 году выдающийся американский математик и инженер Клод Шеннон показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе и для функционирования релейно-контактных и электронно-ламповых схем.
Высказывание
Исследования в алгебре логики тесно связаны с изучением высказываний, вызвано это тем, что высказывания являются одним из основных видов носителей информации. С помощью высказываний устанавливаются свойства, взаимосвязи между объектами.
В формальной логике Аристотель определяет высказывание следующим образом:
Высказывание — это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности.
Однако, определение Аристотеля не является математически точным и порождает ряд парадоксов и противоречий. Это связано с тем, что Аристотель проблему определения высказывания заменяет проблемой определения истинности или ложности предложения.
Например, рассмотрим предложение: «Это предложение является ложным»
- Пусть предложение истинно. Тогда это противоречит его собственному утверждению.
- Пусть предложение ложно. Тогда следует, что предложение на самом деле истинно.
Значит, предложению нельзя приписать какое-либо значение истинности, следовательно, оно не является высказыванием.
Причина данного парадокса лежит в структуре построения указанного предложения: оно ссылается на свое собственное значение. Таким образом, необходимы определенные ограничения на допустимые формы высказываний:
- Определение. Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием.
- Алгебра логики отвлекается от смысловой содержательности высказываний.
Введение таких ограничений дает возможность изучать высказывания алгебраическими методами, т.е. позволяет ввести операции над элементарными высказываниями и с их помощью строить и изучать составные высказывания.
Cоставное высказывание
Определение. Cоставное (cложное) высказывание – это высказывание, построенное из простых высказываний, с помощью логических связок (операций).
В обычной речи, в качестве подобных связок, употребляются «и», «или», «не», «либо…, либо…», «если…, то…», «тогда и только тогда, когда …». Эти связки трактуются как логические операции над высказываниями.
| Логическая операция | Логическая связка | Формальный знак |
|---|---|---|
| Конъюнкция (логическое умножение) | «и» | &, ∧ |
| Дизъюнкция (логическое сложение) | «или» | ∨, + |
| Инверсия (логическое отрицание) | «не» | ¬ |
| Разделительная дизъюнкция (исключающее ИЛИ) | «либо…, либо…» | ⊕, Δ |
| Импликация (логическое следование) | «если…, то…» | ⇒, → |
| Эквивалентность (равносильность) | «тогда и только тогда, когда» | ≡, ↔, ⇔ |
Алгебра логики изучает строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.