Элементы математической логики

1. Высказывания

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

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля.

Так, например, предложение " 6 — четное число " следует считать высказыванием, так как оно истинное. Предложение " Рим — столица Франции " тоже высказывание, так как оно ложное.

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

Для построения сложных высказываний вводятся определенные правила, которые называются операциями над высказываниями.

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

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

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:

Отрицание

x

Конъюнкция x × y " x и y "		Дизъюнкция x Ú y " x или y "
x	y	x × y		x	y	x Ú y
Импликация x ® y " если x, то y "		Эквивалентность x º y " x тогда и только тогда, когда y "
x	y	x ® y		x	y	x º y

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

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”.

Пример: Конъюнкция (логическое произведение) высказываний является ложным высказыванием тогда и только тогда, когда

1) ложным является хотя бы один сомножитель

2) истинными являются оба сомножителя

3) оба сомножителя ложны

4) ложным является только один сомножитель

Дата добавления: 2014-01-11