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

 

 

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

Термин «логика» происходит от греческого слова логос, что означает «мысль», «разум», «слово», «понятие». Логика (или формальная логика) как наука изучает мышление. Но мышление изучается не только логикой, а и различными другими науками: психологией, физиологией, кибернетикой, педагогикой и т. д. Каждая из них изучает какую-то одну из сторон сложного процесса мышления. Логика изучает формы рассуждении, отвлекаясь от их конкретного содержания; устанавливает, что из чего следует, ищет ответ на вопрос: как мы рассуждаем?

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

В работах математиков А.Н. Колмогорова1, Л.П. Стойлова2, A.M. Пышкало3 и др. освещены принципиальные вопросы элементов математической логики, коньюнкции и дизъюнкции высказываний и высказывательных форм.

Объект исследования – математическая логика.

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

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

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

  • рассмотреть основные понятия элементов математической логики;
  • рассмотреть логические функции одной и двух переменных;
  • изучить коньюнкцию и дизъюнкцию высказываний;
  • изучить коньюнкцию и дизъюнкцию высказывательных форм;

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

Методами исследования были определены следующие: теоретический анализ, синтез, сравнение, конкретизация, обобщение учебно-методических, научных, справочных источников по проблеме исследования

Практическая значимость исследования состоит в том, что в процессе работы были получены навыки проведения самостоятельного учебного исследования, что способствовало формированию общих компетенций (ОК), направленных на осознание сущности и социальной значимости профессии (ОК 1), осуществление поиска и использования информации, необходимой для эффективного выполнения профессиональных задач (ОК 4), овладение ИКТ в профессиональной деятельности (ОК 5).

Структура работы состоит из введения, трех глав, заключения, списка литературы.

Во введении обосновывается актуальность, параметры исследования.

В первой главе рассматриваются элементы математической логики.

Во второй главе описаны коньюнкция и дизъюнкция высказываний.

В третьей главе описаны коньюнкция и дизъюнкция высказывательных форм.

В заключении приведены основные выводы исследования.

Список использованных источников содержит десять наименований официальных источников.

Глава 1. Элементы математической логики

 

1.1 Основные  понятия элементов математической  логики

 

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

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

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

«Земля — планета солнечной системы.»

Истина

«2+8<5»

Ложь

«Всякий квадрат есть параллелограмм.»

Истина

«Каждый параллелограмм есть квадрат.»

Ложь


Рис. 1. 1.   – Примеры высказываний

Приведем примеры, предложений не являющихся высказываниями:

«Посмотрите в окно.»

«Который час?»

«2x+7>12»

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

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

Рассмотрим несколько примеров сложных высказываний: 7

«Если идет дождь, то солнце не светит.»

« Если ветер дует, то нет дождя.»

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

Простые высказывания называть логическими переменными и обозначать большими буквами и, если высказывание истинно, будем писать A=1, а если ложно, то A=0.

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

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

Значения логической функции для разных сочетаний значений входных переменных - или, как это иначе называют, наборов входных переменных - обычно задаются специальной таблицей. Такая таблица называется таблицей истинности. Количество наборов входных переменных (Q) можно определить по формуле: 8

Q=2n, где n — количество входных переменных.

Простейшим примером логической функции является функция одной переменной:

Таблица 1

Функция одной переменной

Аргумент

Функция

X

F0(X)

F1(X)

F2(X)

F3(X)

0

0

0

1

1

1

0

1

0

1


F0(X) –  константа 0

F1(X) – переменная X

F2(X) – инверсия X

F3(X) – константа 1

Интересной является только функция F2(X).

Функции двух аргументов. Их может быть 16.

Таблица 2

Функции двух аргументов

Аргументы

Функция

X1

X2

F0

F1

F2

F3

F4

F5

F6

F7

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

Аргументы

Функция

X2

F0

F8

F9

F10

F11

F12

F13

F14

F15

0

0

1

1

1

1

1

1

1

1

1

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

0

0

1

1

1

0

0

1

0

1

0

1

0

1


 

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

 

    1. Логические функции одной и двух переменных

 

Логическое умножение (conjunctio - лат. связываю). Соединение двух простых высказываний A и B в одно составное с помощью союза «и» называют логическим умножением или конъюнкцией, а результат операции — логическим произведением. 9

Указание о логическом перемножении простых высказываний A и B обозначается так:

Таблица 3

Логическое умножение

A

B

A*B

Минск является столицей Белоруссии

В Минске проживает 1543 тыс. человек

Минск является столицей Белоруссии и в Минске проживает 1543 тыс. человек


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

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

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

Таблица истинности конъюнкции имеет следующий вид:

Таблица 4

Таблица истинности конъюнкции

A

B

A*B

0

0

0

0

1

0

1

0

0

1

1

1


 

Следующие логические законы можно назвать свойствами конъюнкции: 10

  1. Закон противоречия.
  2. Закон равносильности (идемпотентности, idem – лат. тот же самый; potens – лат. сильный)
  3. Закон исключения констант

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

1. Рассмотрим повествовательное  предложение: «Володя вчера в  шесть часов вечера читал книгу  или ехал в автобусе на стадион.»  Союз «или» использован в этом  предложении в неисключающем смысле — Володя мог читать и одновременное ехать в автобусе. Одно не исключает другого.

2. Рассмотрим еще одно  повествовательное предложение. «Володя  вчера наблюдал за ходом матча  с западной или восточной трибуны.»  Здесь союз «или» имеет исключающий  характер — две описываемые  ситуации исключают друг друга: нельзя наблюдать один и тот  же матч одновременно с двух  противоположных трибун.

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

Указание о необходимости выполнить логическое сложение высказываний A и B записывается так:

Таблица 5

Логическое сложение высказываний A и B

A

B

A+B

Шесть число кратное 3

19>37

Шесть число кратное 3 или 19>37


 

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

Это определение можно обобщить для любого количества логических0, С=0.

Таблица истинности дизъюнкции имеет следующий вид:

Таблица 6

Таблица истинности дизъюнкции

A

B

A+B

0

0

0

0

1

1

1

0

1

1

1

1


 

Следующие логические законы можно назвать свойствами дизъюнкции: 11

  1. Закон противоречия.
  2. Закон равносильности (идемпотентности idem – лат. тот же самый; potens – лат. сильный) А+А=А
  3. Закон исключения констант А+1=1, А+0=А

Логическое отрицание. (inversio – лат. переворачиваю) Присоединение частицы «не» к сказуемому данного простого высказывания A называется операцией логического отрицания или инверсией. Обозначается A или A¬.

Иногда вместо приведенного определения используют другое, ему эквивалентное: присоединение слов «Неверно, что …» ко всему данному высказыванию A называется операцией логического отрицания. В результате выполнения операции логического отрицания получается новое высказывание.

Таблица 7

Логическое отрицание

А

  

Число 5 является делителем числа 30

Число 5 не является делителем числа 30


 

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

Таблица 8

Таблица истинности инверсии

А

  

0

1

1

0


 

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

Импликация. (implicatio - лат. тесно связываю) или логическое следование соответствует обороту «если…, то…», обозначается

Рис. 1.1.   – Импликация

A={Поезд прибывает на данный путь.}

B={Подается сигнал, что путь закрыт.}

Рассматриваемое сложное высказывание истинно, если:

1) поезд прибывает, сигнал  «закрыт» (1, 1, 1);

2) поезд не прибывает, сигнал «свободен» (0, 0, 1);

3) поезд не пребывает, сигнал «закрыт» (0, 0, 1) – если  поезд не пребывает, безопасен  любой сигнал;

4) высказывание ложно (безопасность  не обеспечивается) только в том  случае, если поезд прибывает, а  сигнал «свободен» (1, 0, 0).

Операция импликации в русском языке является самой «загадочной». Ей соответствую также следующие речевые обороты: «из А следует В»; «А имплицирует В»; «А достаточно для В»; «В необходимо для А».

Рис. 1.2.   – Операция импликации

Эквивалентность. (aequivalens – фр. равноценное) или равнозначность, соответствует оборотам речи «тогда и только тогда» и «в том и только в том случае», обозначается , или или

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

«Петя выучит уроки тогда и только тогда, когда Пете поставят хорошую отметку.»

В русском языке операции эквивалентности также соответствует речевой оборот «A необходимо и достаточно B».

Рис. 1.3.   – Представление эквивалентности через конъюнкцию, дизъюнкцию и инверсию

Строгая дизъюнкция или Сложение по модулю «2», соответствует оборотам речи «или…, или…» или «либо…, либо…», и обозначается

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

Представление эквивалентности через конъюнкцию, дизъюнкцию и инверсию =A*+*B.

 Сравнив таблицы истинности операций эквивалентности и сложения по модулю 2, можно сделать вывод, что эти сравнения являются инверсией друг друга, то есть A↔B=

Таблица 9

Таблица истинности инверсии

A

B

0

0

0

0

1

1

1

0

1

1

1

0


 

Рис. 1.4.   – Cвойства строгой дизъюнкции

Стрелка Пирса (символ Лукашевича) – логическая операция с двумя переменными, соответствует обороту речи «ни…ни», обозначается следующим образом F(A,B)=A↓B.

Выражение A↓B истинно в том и только том случае, когда оба высказывания А и В ложные.

A↓B =.

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

=A↓A

A*B=( A↓A)↓(B↓B)

A+B=( A↓B)↓(A↓B)

Cвойства Стрелки Пирса:

A↓A=

A↓=0

A↓0=

A↓1=0

Таблица 10

Таблица Стрелки Пирса

A

B

A↓A

0

0

1

0

1

0

1

0

0

1

1

0


 Штрих  Шеффера - – логическая операция с двумя переменными, соответствует обороту речи «не…не», обозначается следующим образом F(A,B)=A│B.

Выражение A│B ложно в том и только том случае, когда оба высказывания А и В истинны.

A│B =.

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

= A│B

A*B=( A│B)│(A│B)

A+B=( A│A)│(B│B) A│B)↓(A↓B)

Cвойства Стрелки Пирса:

A│A=

A│=1

A│0=

A│1=

Краткие выводы по первой главе

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2. Конъюнкция и дизъюнкция высказываний и высказывательных форм

 

2.1. Конъюнкция и дизъюнкция высказываний

 

Конъюнкцией высказываний А и В называется высказывание А∧В, которое истинно, когда оба высказывания истинны, и ложно, когда хотя бы одно из высказываний ложно. 12

Обозначают А∧В (читают: «А и В»).

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

А

В

А∧В

и

и

и

и

л

л

л

и

л

л

л

л


 

 

Рис. 2.1.   – Таблица истинности

Используя данное определение, находим значение истинности высказывания «число 28 делится на 7 и на 9», которое, как было установлено раньше, состоит из двух элементарных высказываний, соединенных союзом «и», т.е. является конъюнкцией. Так как первое высказывание истинно, а второе ложно, то, согласно определению конъюнкции, высказывание «число 28 делится на 7 и на 9» будет ложным.

Данной операции соответствует логическая связка И и символ  либо

Конъюнкцией высказываний  и  называют высказывание  (читается «а и бэ»), которое истинно в том и только том случае, когда истинны оба высказывания  и :

Рис. 2.2.   – Конъюнкция высказываний

Данная операция тоже встречается сплошь и рядом. Предположим, что Петя получает допуск к экзамену по высшей математике, если сдаёт курсовую работу и зачёт по теме. Рассмотрим следующие высказывания:

 – Петя сдал курсовую работу;

 – Петя сдал зачёт.

Заметьте, что в отличие от формулировки «Петя завтра сдаст» здесь уже в любой момент времени можно сказать, истина это или ложь.

Высказывание  (суть – Петя  допущен к экзамену) будет истинно в том и только том случае, если он сдал курсовик  и зачёт по . Если хоть что-то не сдано (см. три нижних строчки таблицы), то конъюнкция  – ложна.

Знак системы  соединяет входящие в неё уравнения/неравенства как раз по правилу И. Так, например, запись двух линейных уравнений  в систему  подразумевает то, что надо найти ТАКИЕ корни  (если они существуют), которые удовлетворяют и первому и второму уравнению.

Рассматриваемая логическая операция распространяется и на большее количество высказываний. Условно говоря, если в системе 5 уравнений, то её корни (в случае их существования) должны удовлетворять и 1-му и 2-му и 3-му и 4-му и 5-му уравнению данной системы.

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

 – выключатель в комнате включен;

 – рубильник в подъезде включен.

Конъюнкция читается самым что ни на есть естественным образом: 
 – выключатель в комнате включен и рубильник в подъезде включен.

Очевидно, что  тогда и только тогда, когда . В трёх других случаях (проанализируйте, каких) цепь разомкнётся и свет погаснет: .

Присоединим ещё одно высказывание: 
 – рубильник на подстанции включен.