Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Основные логические операции и правила их выполнения.




Логические основы ЭВМ.

 

 

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

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

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

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

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание "площадь поверхности Индийского океана равна 75 млн кв. км" в одной ситуации можно посчитать ложным, а в другой – истинным. Ложным – так как указанное значение неточное и вообще не является постоянным. Истинным – если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

Так, например, из элементарных высказываний "Петров – врач", "Петров – шахматист" при помощи связки "и" можно получить составное высказывание "Петров – врач и шахматист", понимаемое как "Петров – врач, хорошо играющий в шахматы".

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

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В – высказывание "Тимур летом отправится в горы". Тогда составное высказывание "Тимур летом побывает и на море, и в горах" можно кратко записать как А и В. Здесь "и" – логическая связка, А, В – логические переменные, которые могут принимать только одно из двух значений – "истина" или "ложь", обозначаемые, соответственно, "1" и "0".

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

В алгебре высказываний над простыми высказываниями определены следующие операции:

- " или " – логическое сложение (дизъюнкция);

- " и " – логическое умножение (конъюнкция);

- " не " – логическое отрицание.

- " если..., то " – логическое следование (импликация);

- " тогда и только тогда " – эквивалентность;

Рассмотрим эти логические операции.

Логическое сложение. Это сложное суждение, которое может быть составлено из нескольких простых высказываний. Своим названием обязано латинскому disjunctio – разоблачение, различие. Значение этого сложного высказывания будет истина тогда и только тогда, когда истинно хотя бы одно из входящих в него суждений. Пусть число входящих в него высказываний будет минимальным и равно двум. Обозначим эти высказывания А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.2, которая называется таблицей истинности.

Таблица 2.2

Таблица истинности

А В Y     или A B Y
истинно истинно истинно      
истинно ложно истинно      
ложно истинно истинно      
ложно ложно ложно      

 

Для обозначения дизъюнкции используется знак "+" и записывается

 

Y=А+В

Это логическое сложение, поэтому:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Логическое умножение. Это также сложное высказывание, которое может быть составлено из нескольких простых высказываний. Своим названием обязано латинскому conjunctio – соединяю. По определению конъюнктивным называется сложное высказывание, которое истинно тогда и только тогда, когда истинны все входящие в него высказывания. Как и в предыдущем случае рассмотрим пример с двумя высказываниями А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.3, которая называется таблицей истинности.

Таблица 2.3

Таблица истинности

А В Y     или A B Y
истинно истинно истинно      
истинно ложно ложно      
ложно истинно ложно      
ложно ложно ложно      

 

Для обозначения конъюнкции используется знак "*" и записывается

 

Y=А*В

и

0 * 0 = 0

0 * 1 = 0

1 * 0 = 0

1 * 1 = 1

Логическое отрицание. Присоединение частицы "НЕ" к сказуемому данного простого высказывания А называется операцией логического отрицания. Операция логическое отрицание над высказыванием А записывается А. Возможные наборы значений и итогового высказывания Y можно изобразить с помощью таблицы 2.4, которая называется таблицей истинности.

Таблица 2.4

Таблица истинности

А Y = А     или A Y
истинно ложно    
ложно истинно    

 

Логическое следование. Соединение двух высказываний в одно с использованием оборота речи "Если …, то…" называется операцией логического следования или импликацией. Операция импликации над высказываниями А и В записывается А → В (читается "А имплицирует В" или "В следует из А"). По определению импликацией называется сложное высказывание, которое ложно тогда и только тогда, когда А – истинно, а В – ложно. Рассмотрим пример с двумя высказываниями А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.5, которая называется таблицей истинности.

Таблица 2.5

Таблица истинности

А В Y=А→В     или A B Y=А→В
истинно истинно истинно      
истинно ложно ложно      
ложно истинно истинно      
ложно ложно истинно      

 

Эквивалентность. Соединение двух простых высказываний А и В в одно с использованием оборота речи, или, как принято говорить, связки "…тогда и только тогда…", называется операцией эквивалентности. Многоточием помечены высказывания, над которыми проводится операция эквивалентности. Операция эквивалентности над высказываниями А и В записывается А~B (читается "А эквивалентно В"). Эквивалентностью называется сложное высказывание, которое истинно тогда и только тогда, когда А и В – одновременно истинны или ложны. Рассмотрим пример с двумя высказываниями А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.6, которая называется таблицей истинности.

Таблица 2.6

Таблица истинности

А В Y=А~В     или A B Y=А~В
истинно истинно истинно      
истинно ложно ложно      
ложно истинно ложно      
ложно ложно истинно      

 

Три логические операции: дизъюнкция, конъюнкция и отрицание составляют "полную систему" – это значит, что любое логическое выражение можно составить с использованием только этих трех операций. Например, операцию импликации А→В можно заменить на 1-А+А*В, а операцию эквивалентность А~В заменить на 1-(А-В)2.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...