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

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

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

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

Логика предикатов (predicate logic) есть формальная сис­тема, предметом которой являются предложения с учетом их внутренних состава и струк­туры.

Логика реляционная (relation logic ) есть формальная система, предметом кото­рой являются отношения в виде множества однородных предложений, существенно расширяющие логику предикатов.

Логика нечеткая (fuzzi logic ) есть также формальная система, предметом кото­рой являются предложения при нечетком задании - характер­ных признаков отдельных составляющих элементов или отношений между ними.

Логика высказываний

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

Например, предложение "З - простое число" является истинным, а “3.14… - рациональное число" – ложным; "Колумб открыл Америку" - истинным, а "Киев - столица Узбекистана" – ложным; “число 6 делится на 2 и 3” – истинным, а “сумма чисел 2 и 3 равна 6” – ложным и т.п.

Такие высказывания называют простыми или элементарными.

При формальном исследовании сложных текстов понятие “простые высказывания” замещают понятием “ пропозициональные переменные ”, которые обозначают прописными буквами латин­ского алфавита “A”, “B”, “C”,… Истинность или ложность высказывания будем отмечать символами “и” – истина или “л” – ложь.

Пример:

· если A₁:=“3 - простое число”, то A₁ = и;

· если A₂:=“3 - вещественное число”, то A₂ = и;

· если A₃:=“3 - целое число”, то A₃ = и;

· если B₁:=“3, 14…- рациональное число”, то B₁ = л;

· если B₂:=“3, 14…- не рациональное число”, то B₂ = и;

· если C:=“Колумб открыл Америку”, то C = и;

· если D:=“Киев - столица Узбекистана”, то D = л;

· если E:= “Число 6 делится на 1, 2 и 3”, то E = и;

· если G:=“Число 6 есть сумма чисел 1, 2, 3”, то G = и.

Примечание: символ “:=” означает, что пропозициональной переменной, стоящей слева, присвоить значение высказывания, стоящего справа.

Высказывания, которые формируют из простых предложений с помощью грамматических связок “не”, “и”, “или”, “если…, то…”,

“… тогда и только тогда, когда…” и т.п., называют сложными. Для обозначения грамматических связок в формальном языке вводят символы, которые называют логическими связками.

Например, Ú:=”или”, &:=“и”, ù:=”не”, ®:=“если…, то…”, «:=“…тогда и только тогда, когда …”.

Для построения более сложных высказываний используют вспомогатель­ные символы “(“, “)” - скобки.

Пример:

· если высказывание: “3 – вещественное и целое число”, то формула (A₁&A₂) = и;

· если высказывание: ”3,14… - рациональное число”, то формулы B₁=л или ùB₁ = и;

· если высказывание: “число 6 делится на 1, 2, 3 и представляет сумму делителей 1, 2, 3”, то формула (E&G)= и;

· для высказывания: “если 3 - целое число, то оно вещественное”, справедлива формула (A₃® A₂)=и;

· для высказывания ”если 3 – простое число, то оно целое”, справедлива формула (A₁® A₃)=и;

· для высказывания “3 - простое число тогда и только тогда, когда оно целое”, справедлива формула (А₁«А₂)=и.

Обозначения элементарных высказываний А₁, А₂, А₃, В₁, Е, G взяты из предыдущего примера.

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

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

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

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

Высказывания, из которых делают вывод новых высказываний, называют посылками, а получаемое высказывание – заключением.

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

Совокупность пропозициональных переменных T={A, B, C,…} и логических операций F ={ù; &; Ú; ®; «} формируют алгебру высказываний:

A_в=< T; F >.

Символы логических операций заданы логическими связками:

ù - отрицание, & - конъюнкция, Ú - дизъюнкция, ® - импликация, « - эквиваленция.

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

Любая пропозициональная переменная есть элементарная формула, т. е. A_i =F_i.

Если F₁ и F₂ –формулы, то ùF₁, ùF₂, (F₁&F₂), (F₁ÚF₂), (F₁®F₂) и (F₁«F₂) также формулы.

Никаких других формул в исчислении высказываний нет.

Значение формулы полностью определяется значениями входящих в нее пропозициональных переменных.

Логические операции

Логические операции бывают унарными (или одноместными) и бинарными (или двухместными). Это определяется наличием одного или двух операндов. Результаты логических операций также принадлежат множеству {и; л} и их удобно описывать таблицами истинности.

Отрицание (ù F) есть одноместная операция, посредством кото­рой ее значение есть отрицание значения операнда.

В программировании для этого используют оператор NOT: (NOT F) истинно тогда и только тогда, когда F ложно.

 

F	ùF	Если F - высказывание, то ùF также высказывание.
и	л	Если ùF есть высказывание, то ù(ùF) также есть высказывание.
л	и

 

Пример: верно ли, что высказывание “А:=“4 - простое число” истинно?

Нет, “неверно, что 4 –простое число”. Тогда ù А = и.

Конъюнкция (F₁ & F₂) есть двухместная операция, посредст­вом которой из двух формул F₁ и F₂ получают новую формулу F =(F₁&F₂), описывающую сложное высказывание.

В про­граммировании для этого используют оператор AND:

(F₁_AND_F₂) истинно тогда и только тогда, когда истинны значения двух операндов F₁ и F₂.

.

F1	F2	F1&F2		Если даны формулы F1, F2,…Fn, то формула F=(F1&F2&…&Fn)=и тогда и только тогда, когда истинны все формулы F1, F2,…Fn.
л	л	л
л	и	л
и	л	л
и	и	и

Из определения операций коньюнкции и отрицания очевидно, что (F&ùF)=л.

На естественном языке эта операция выражается соединительными словами: “..и..“, “..также..“, “как..,так..“, “..несмотря на..“ и др.

Пример: даны высказывания A:="компьютер содержит основной микропроцессор", B:="компьютер содержит оперативную память", C:=”компьютер содержит контроллеры"; D:="компьютер содержит порты ввода - вывода".

Тогда формула F = (A&B&C&D) отражает высказывание "компью­тер содержит основной микропроцессор, оперативную память, контроллеры и порты ввода-вывода".

Дизъюнкция (F₁ÚF₂) есть двухместная операция, посред­ством которой из двух формул F₁ и F₂ получают новую формулу F=(F₁ÚF₂), описывающую сложное высказывание.

В программировании для этого используют оператор OR:

(F₁_ OR _F₂) ложно тогда и только тогда, когда ложны значения двух операндов F₁ или F₂..

Таблица истинности операции дизъюнкции представлена справа. Из определения операций дизьюнкции и отрицания очевидно, что (FÚùF)=и.

В естественном языке эта операция выражается разъединительными словами “..или..“, “..либо.. “ и т.п..

 

	F1	F2	F1ÚF2	Если даны формулы F1, F2,…Fn, то значение формулы F=(F1ÚF2Ú…ÚFn)=и определяется значением “и” хотя бы одной формулы F1, F2,…или Fn.
л	л	л
л	и	и
и	л	и
и	и	и

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

Пример: даны высказывания A:="в компьютере применяют матричный принтер", B:="в компьютере применяют струйный принтер", C:="в компьютере применяют лазерный принтер"; D:="в компьютере применяют литерный принтер".

Тогда формула F = (AÚBÚCÚD) отражает высказывание " в компьютере применяют матричный, струйный, лазерный или литерный принтеры".

Импликация (F ₁®F₂) есть двуместная операция, посредством ко­торой выражают сложное высказывание. Значение этого высказывания

В программировании используют оператор IMPLIES:

(F₁ IMPLIES F₂) ложно тогда и только тогда, когда истинно F₁ и ложно F₂..

 

F1	F2	F1®F2	На естественном языке эта операция выражается словами "если..., то... ", "тогда..., когда... ", "постольку..., поскольку... ", "при наличии..., следует... ", и т. п.. F1 называют посылкой, а F2 – заключением
л	л	и
л	и	и
и	л	л
и	и	и

.

Пример: даны высказывания A:="по проводнику протекает электричес­кий ток" и B - "вокруг проводника есть магнитное поле".

Тогда формула F=(A®B) отражает высказывание "если по проводнику протекает электрический ток, то вокруг проводника возникает магнитное поле".

Эквиваленция (F₁«F₂) есть двухместная операция, посредством ко­торой из двух формул F₁ и F₂ получают новую формулу F = (F₁«F₂),описывающую сложное высказывание.

В программирова­нии для этого используют оператор IFF:

(F_{1_}_IFF F ₂) истинно тогда и только тогда, когда оба операнда F₁ и F₂ имеют одинаковые значения..

 

F1	F2	F1«F2	На естественном языке эквиваленция выражается словами " для того, чтобы.., необходимо и достаточно..", ".. лишь при ус­ловии.." и т. п.
л	л	и
л	и	л
и	л	л
и	и	и

 

Пример: даны высказывания A:=“выполнить загрузку в компьютер операцион­ной системы” и B:=“установить в компьютер диске­ту с записанной операционной системой“.

Тогда формула F =(A«B) отображает высказывание “для того, чтобы выпол­нить загрузку операционной системы в компьютер, необходимо и достаточно установить в компьютер дискету с запи­санной операционной системой".

Пример: даны высказывания A:=”урожай будет стабильным еже­годно” и B:="выполнены все ирригационные работы".

Тогда формула F =(A«B) отображает высказывание "урожай будет еже­годно стабильным тогда и только тогда, когда будут выполне­ны все ирригационные работы".

⇐ Предыдущая13141516171819202122Следующая ⇒

Поделиться:

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