Алгебра высказывавнии

МОСКОВСКИЙ УНИВЕРСИТЕТ ЭКОНОМИКИ, СТАТИСТИКИ И ИНФОРМАТИКИ (БРЯНСКИЙ ФИЛИАЛ)

 

 

РЕФЕРАТ ПО ДИСЦИПЛИНЕ  "ЭЛЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ"

ТЕМА РЕФЕРАТА

" Алгебра высказывании "

 

 

 

 

Выполнил: Студент 2 курса гр. ДЛП - 201

Ильичев Владислав

 

ПРОВЕРИЛ: преподователь математики

Приходько Ю.В.

 

Оценка за доклад: ________

Дата проверки: __________

 

 

 

Брянск 2014

 

Содержание

1. Введение с.3
2. Понятие высказывания. Операции над простыми высказываниями. Таблицы истинности с.4-9
3. Примеры построения таблиц истинности сложных высказываний с.10-12
4. Логические законы с.13-15
5. Решение логических задач с.16-19
6. Диаграммы Эйлера-Вена с.20-21
7. Заключение с.22
8. Список литературы с.23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

Одна из главных задач логики - определить, как прийти к выводу из предпосылок. Логика служит базовым инструментом почти любой науки. Основателем логики считают Сократа. Позднее из логики стала выделяться самостоятельная часть – математическая логика, изучающая основания математики и принципы построения математических теорий.

 

 

 

 

 

 

 

 

 

 

Понятие высказывания. Операции над простыми высказываниями. Таблицы истинности

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

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

Логическими значениями высказываний является "истина" и "ложь". Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным. Приведем примеры высказываний:

1) Москва - столица России;

2) число 27 является простым;

3) Волга впадает в Каспийское  море.

Высказывания 1 и 3 являются истинными. Высказывание 2 - ложным, потому что число 27 составное 27=3*3*3.

Следующие предложения высказываниями не являются:

1) давай пойдем гулять;

2) 2*x>8;

3) a*x2+b*x+c=0;

4) который час?

Подчеркнем еще раз, что отличительным признаком высказывания является свойство быть истинным или ложным, последние четыре предложения этим свойством не обладают. Невозможно отнести неравенство 2 или уравнение 3 к высказываниям пока не определено значение x. При x=3 высказывание "2*3>8" ложно, а при x=5 "2*5>8" - истинно.

Условимся обозначать высказывания большими буквами и, следуя Джорджу Булю, истинное (true) высказывание A обозначим так, A=1. В том случае, когда A - ложное (false) высказывание, будем писать: A=0.

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

1) логическое отрицание (NOT). Логическое сложение, умножение, следование  и эквивалентность являются бинарными операциями ("би" - два), потому что соединяют два операнда (два высказывания). В отличие от них, логическое отрицание является унарной операцией, потому что применяется лишь к одному высказыванию.

Присоединение частицы НЕ к сказуемому простого высказывания A называется операцией логического отрицания. Для обозначения отрицания высказывания A обычно пишут: Ā;

2) логическое умножение (AND). Соединение двух простых высказываний A и B в одно составное с помощью  союза И называется логическим умножением или конъюнкцией, а результат операции логическим произведением.

Указание о логическом умножении двух высказываний A и B обозначают так: AΛB. Результат логического умножения AΛB имеет истинное значение лишь в том случае, когда и A, и B истинны;

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

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

4) логическое следование  или импликация. Соединение двух простых высказываний A и B в одно с использованием оборота речи "ЕСЛИ :, ТО :" называется операцией логического следования или импликацией.

Указание выполнить операцию импликации над высказываниями A и B записывается так: A → B (читается "A имплицирует B" или "B следует из A");

5) эквивалентность. Соединение  двух простых высказываний A и B в  одно с использованием оборота  речи ":ТОГДА И ТОЛЬКО ТОГДА, КОГДА" : называется операцией эквивалентности.

Выcказывания, над которыми выполняется операция эквивалентности, помещают вместо многоточия. Указание выполнить операцию эквивалентности над высказываниями A и B записывается так: A ~ B (читается "A эквивалентно B").

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

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

Рассмотрим построение таблиц истинности на примере операций, рассмотренных в предыдущем разделе. Начнем с унарной операции отрицания Ā. Поскольку операция выполняется над одним операндом (A), принимающим всего два значения ( 1-истина; 0-ложь), таблица будет иметь три строки и два столбца. В заголовке таблицы укажем высказывание A и результат отрицания Ā, как показано на рисунке.

 

A	Ā

 

Далее в первом столбце разместим все возможные значения высказывания A, а во втором - значения логической функции Ā, как показано на рисунке.

 

A	Ā
0	1
1	0

 

Приведем таблицу истинности логического умножения (конъюнкции).

 

A	B	A Λ B
0	0	0
0	1	0
1	0	0
1	1	1

 

Заметим, что составное высказывание A Λ B истинно только в том случае, когда истинны ода высказывания и A, и B.

Таблица истинности логического сложения приведена на следующем рисунке.

 

A	B	A V B
0	0	0
0	1	1
1	0	1
1	1	1

 

Составное высказывание A V B ложно лишь в случае, когда оба операнда ложны. Таблица истинности импликации, выглядит следующим образом:

 

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

 

Составное высказывание A → B ложно лишь в случае, когда ложь имплицируется истиной.

Таблица истинности эквивалентности представлена на следующем рисунке.

 

A	B	A ~ B
0	0	1
0	1	0
1	0	0
1	1	1

 

Составное высказывание A ~ B истинно в том случае, когда значения операндов совпадают. Полезно иметь под рукой сводную таблицу истинности.

 

Сводная таблица истинности

A 0 0 1 1 B 0 1 0 1 Коньюнкция A Λ B 0 0 0 1 Дизъюнкция A V B 0 1 1 1 Импликация A → B 1 1 0 1 Эквиваленция A ~ B 1 0 0 1

 

 

Примеры построения таблиц истинности сложных высказываний

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

Задача. Составить таблицу истинности высказывания

Решение.

Данное высказывание состоит из двух операндов A и B. Для его вычисления необходимо сначала вычислить отрицание A, то есть Ā , затем , далее выполнить логическое умножение , затем сложение и, наконец, отрицание . Таким образом, в таблице истинности будет 7 столбцов и 5 строк.

 

A	B	Ā

 

Заполняем ячейки, соответствующие значению всем возможным сочетаниям значений высказываний A и B.