Лекция 2. Логика (от греческого слова «logos» - слово, мысль, речь, разум) – совокупность наук о законах и формах мышления

Тема: «Алгебра логики».

Логика (от греческого слова «logos» - слово, мысль, речь, разум) – совокупность наук о законах и формах мышления, о наиболее общих законах мышления. Начало исследований в области формальной логики было положено работами Аристотеля в IV веке до н.э. Логика оперирует понятиями, суждениями и умозаключениями. В середине XIX века возникли и начали интенсивно развиваться математические средства и методы. Именно она заложила теоретические основы последующей разработки языков программирования.

Одним из основных разделов математической логики является алгебра логики (исчисление высказываний), основоположником которой был Джордж Буль (1815-1864), положивший в основу своего логического учения методы алгебры (алгебра Буля).

1. Алгебра логики в современном изложении занимается исследованием операций с высказываниями.

Высказывание – это истинное или ложное предложение.

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

Например:

«истинные» - «Земля – планета Солнечной системы», «два умножить на два равно четыре», «три – простое число», «ребята – не Москва ль за нами»;

«ложные» - «Марс – не планета Солнечной системы», «пять меньше двух».

Предложения: «Будь осторожен!», «Справишься ли ты с заданием?» - не являются высказываниями.

Вопрос об истинности простых высказываний лежит вне сферы логики – на него отвечают конкретные науки, повседневная практика или наблюдения! Высказывания обычно обозначаются большими буквами латинского алфавита. Если высказывание А истинно, будем писать А=1, если ложно, то А=0.

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

Логическая связка отрицание: в естественном языке ему соответствует выражение «неверно, что…», относящееся ко всему высказыванию, или присоединение союза «не» к некоторой части простого высказывания.

Например: если А – простое высказывание «Идет дождь», то отрицанием А (пишется: ) является высказывание «Неверно, что идет дождь» или «Дождь не идет». Отрицанию соответствует таблица истинности:

А

Логическая связка конъюнкция: в естественном языке ей соответствуют союзы «и», «а», «но», «но», «до», «однако», «хотя» и т.п. Возможны различные варианты записи конъюнкции: F=A^B; F=A*B; F=A&B, иногда даже знак конъюнкции опускается в сложное высказывание записывается следующим образом: F=AB. Иногда конъюнкцию называют логическим произведением.

А	В	А^В

Например: если А – «3-простое число» - истина; В – «3*2=6» - «истина»; то А^В: «3 – простое число и 3*2=6» - «истина».

Логическая связка дизъюнкция: в естественном языке ей соответствует союз «или», который может употребляться в двух разных смыслах: нестрогое «или» - когда члены дизъюнкции не исключают друг друга, то есть могут быть одновременно истинными, и строгое «или» (часто заменяется союзом «либо…, либо…») – когда члены дизъюнкции исключают друг друга.

Нестрогая дизъюнкция обозначается или F=AB; F=A+B.

Нестрогая дизъюнкция: Сложные высказывания, получаемые из двух простых

А	В	АВ

Например, если А – «Школьники в спортзале делают упражнения

на брусьях».

В – «Школьники в спортзале делают упражнения на турнике;

то AB – «Школьники в спортзале делают упражнения на брусьях

или на турнике».

Строгая дизъюнкция. Обозначается или F=AB, или F=AB, или F=A+B.

А	В	АВ

Например, если А – «Школьники в спортзале играют в волейбол»,

В – «Школьники в спортзале играют в баскетбол;

то AB – «Школьники в спортзале играют в волейбол или в

баскетбол».

2.Тождественные преобразования над высказываниями.

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

Высказывания, у которых совпадают таблицы истинности, называют равносильными. Составим следующую таблицу:

А	В	АВ	ВА

Из этой таблицы равносильность высказываний

записанных формулами АВ, ВА. Для обозначения

равносильности будем использовать знак =. Т.о.,

АВ=ВА.

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

А	В	АВ	ВА

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

Например, тождественно истинные формулы:

А=1;

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

Например, ВА=В0

С(В)=С1

3. Свойства отдельных операций.

Операции конъюнкции: АВ=ВА. (AB)С=A(BC) AA=A A1=A A0=0

Операции дизъюнкции: АВ=ВА A(ВС)= (AB)C AA=A A1=A A0=A

Отрицание:=А

=0

=1

Взаимные распределительные свойства:

1. A(ВС)= ABАC

A(ВС)= ABC

2. A(ВС)= (AB)(АC)

A(ВС)= ABC

3.

Формулы де Моргана:

Применяя формулы Моргана, можно любую сложную формулу записать так, чтобы знак отрицания распространялся только на простые высказывания.

Например, ,

3. Законы алгебры логики.

1.Свойства опер. отрицания, конъюнкции и дизъюнкции:

1=0

2. Закон идемпотентности:

устанавливает, что повторяющиеся переменные в выражении излишни и их можно опустить, Т.о., понятие возведение в степень и умножение на коэффициенты, отличные от логических 0 и логических 1 (то есть числа, не имеют смысла.

3. Закон двойного отрицания.

устанавливает, что дважды выполнение отрицание эквивалентно пустой операции.

4. Закон коммутативности:

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

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

6. Закон де Моргана.

описывает эффект отрицания переменных, связанных операциями И и ИЛИ.

7. Согласно закону ассоциативности:

переменные можно группировать в любом порядке как для операций конъюнкции, так и для операций дизъюнкции.

8. Закон дистрибутивности:

х(уz)=(xy)(xz) х(уz)=(xy)(xz)

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

9. Закон двойственности: (если Х - равносильно У, где Х и У – формулы указанного вида, то при замене в каждой из них всех знаков дизъюнкции на знак конъюнкции и наоборот, символа 1 на 0 и наоборот, равносильность сохраняется.

Например: из равносильности

A(ВС)= (AB)(АC) вытекает

A(ВС)= (AB)(АC)

Из равносильности: , вытекает

Контрольные вопросы.

1. Дайте определение логики.
2. Какие высказывания называются ложными, а какие истинными?
3. Какие логические связки существуют для составления сложных высказываний?
4. Какие высказывания называются тождественно истинными?
5. Какие законы алгебры логики используют для тождественных преобразований выражений?

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