Алгебра логики. Понятие высказывания.

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

Логика появилась приблизительно в IV веке до нашей эры. Основоположником формальной логики принято считать выдающегося древнегреческого философа Аристотеля. Он систематизировал различные научные сведения, сформулировал формы и правила логического мышления. Труды, посвященные логике, Аристотель описал в цикле философских сочинений, известных под названием «Органон».

Впервые алгебраические методы для решения традиционных логических задач применил основатель математической логики английский математик и логик Джордж Буль. Свои исследования он опубликовал в работах «Математический анализ логики» (1847), «Логическое исчисление» (1848), «Исследование законов мышления» (1854).

Спустя почти 100 лет в 1938 году выдающийся американский математик и инженер Клод Шеннон показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе и для функционирования релейно-контактных и электронно-ламповых схем.

Высказывание

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

В формальной логике Аристотель определяет высказывание следующим образом:
Высказывание — это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности.

Однако, определение Аристотеля не является математически точным и порождает ряд парадоксов и противоречий. Это связано с тем, что Аристотель проблему определения высказывания заменяет проблемой определения истинности или ложности предложения.

Например, рассмотрим предложение: «Это предложение является ложным»

  • Пусть предложение истинно. Тогда это противоречит его собственному утверждению.
  • Пусть предложение ложно. Тогда следует, что предложение на самом деле истинно.

Значит, предложению нельзя приписать какое-либо значение истинности, следовательно, оно не является высказыванием.

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

  • Определение. Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием.
  • Алгебра логики отвлекается от смысловой содержательности высказываний.

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

Cоставное высказывание

Определение. Cоставное (cложное) высказывание – это высказывание, построенное из простых высказываний, с помощью логических связок (операций).

В обычной речи, в качестве подобных связок, употребляются «и», «или», «не», «либо…, либо…», «если…, то…», «тогда и только тогда, когда …». Эти связки трактуются как логические операции над высказываниями.

Логическая операцияЛогическая связкаФормальный знак
Конъюнкция (логическое умножение)«и»&, ∧
Дизъюнкция (логическое сложение)«или»∨, +
Инверсия (логическое отрицание)«н廬
Разделительная дизъюнкция (исключающее ИЛИ)«либо…, либо…»⊕, Δ
Импликация (логическое следование)«если…, то…»⇒, →
Эквивалентность (равносильность)«тогда и только тогда, когда»≡, ↔, ⇔

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