Логическая связка указывает на необходимость исполнения логической операции над пропозициональными переменными или формулами, окружающими логическую связку.
Логические операции бывают унарные (или одноместные) и бинарные (или двухместные). Этому отвечает наличие одного или двух операндов у данной операции.
Значение формулы полностью определяется значениями входящих в нее пропозициональных переменных.
Значения логических операций также принадлежат множеству {и; л}.
Все значения логической формулы в зависимости от значений входящих в нее элементарных высказываний, могут быть полностью описаны с помощью таблицы истинности.
Отрицание (ùF) есть одноместная операция, посредством которой ее значение есть отрицание значения операнда. В программировании для этого используют оператор NOT:
NOT F истинно тогда и только тогда, когда F ложно.
F |
ùF |
||
|
и |
л |
||
|
л |
и |
На естественном языке эта операция определяет высказывание “неверно, что F истинно (ложно)”.
Если F есть высказывание, то ùF также высказывание. Если ùF есть высказывание, то ù(ùF) также есть высказывание.
Пример: Пусть есть высказывание “А:=“4 — простое число”.
Такое высказывание ложно или “неверно, что 4 –простое число”, т.е.
ù А = и ;
Пусть высказывание D:=“Киев — столица Узбекистана”.
Такое высказывание ложно или “неверно, что Киев – столица Узбекистана”, т.е. ù D = и.
Конъюнкция (F1&F2) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F = F1&F2, описывающую сложное высказывание. Значение этого высказывания истинно тогда и только тогда, когда истинны значения двух операндов F1 и F2.
В программировании для этого используют оператор AND:
F1 AND F2 истинно тогда и только тогда, когда истинны F1 и F2.
F1 |
F2 |
F1&F2 |
||
|
л |
л |
л |
||
|
л |
и |
л |
||
|
и |
л |
л |
||
|
и |
и |
и |
Из определения операций коньюнкции и отрицания очевидно, что (F&ùF)=л.
Если даны формулы F1, F2,…Fn, то истинное значение формулы
F= F1&F2&…&Fn определяется истинностью всех формул F1, F2,…Fn.
На естественном языке эта операция выражается соединительными словами:
“..и..“, “..также..“, “как ..,так..“, “..несмотря на ..“ и т.п.
Пример: Пусть даны высказывания A:=»компьютер содержит основной микропроцессор», B:=»компьютер содержит оперативную память», C:=”компьютер содержит контроллеры»; D:=»компьютер содержит порты ввода — вывода».
Тогда формула F = (A&B&C&D) отражает высказывание «компьютер содержит основной микропроцессор, оперативную память, контроллеры и порты ввода-вывода» [8].
Дизъюнкция (F1ÚF2) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F= F1ÚF2, описывающую сложное высказывание. Значение этого высказывания ложно тогда и только тогда, когда ложны значения двух операндов F1 или F2.
В программировании для этого используют оператор OR:
F1 OR F2 ложно тогда и только тогда, когда ложны F1 и F2.
|
F1 |
F2 |
F1Ú F2 |
||
л |
л |
л |
||
|
л |
и |
и |
||
|
и |
л |
и |
||
|
и |
и |
и |
Из определения операций дизьюнкции и отрицания очевидно, что (FÚùF)=и.
Если даны формулы F1, F2,…Fn, то истинностное значение формулы
F= F1ÚF2Ú…ÚFn определяется истинностью хотя бы одной формулы F1, F2,…или Fn.
В естественном языке эта операция выражается разъединительными словами “..или..“, “..либо.. “ и т.п. Следует обратить внимание, что в повседневной речи союз “или” употребляется в двух смыслах: “исключающее или”, когда истинность составного высказывания определяется истинностью только одного из высказываний, и “не исключающее или”, когда истинность составного высказывания определяется истинностью хотя бы одного из высказываний.
Пример: Пусть даны высказывания A:=»монитор есть машинная программа, которая наблюдает, регулирует, контролирует или проверяет операции в системе обработки данных», B — «монитор в языках программирования есть высокоуровневый механизм взаимодействия и синхронизации процессов, обеспечивающий доступ к неразделяемым ресурсам” и C — «монитор есть дисплей, используемый для контроля процессов и управления системой».
Тогда формула F = (AÚBÚC) отражает высказывание «монитор есть машинная программа, которая наблюдает, регулирует, контролирует или проверяет операции в системе обработки данных, или в языках программирования — это высокоуровневый механизм взаимодействия и синхронизации процессов, обеспечивающих доступ к неразделяемым ресурсам или дисплей, используемый для контроля процессов и управления системой»[8].
Пример: Пусть даны высказывания A:=»в компьютере применяют матричный принтер», B:=»в компьютере применяют струйный принтер», C:=»в компьютере применяют лазерный принтер»; D:=»в компьютере применяют литерный принтер».
Тогда формула F = (AÚBÚCÚD) отражает высказывание » в компьютере применяют матричный, струйный, лазерный или литерный принтеры»[8].
Импликация (F1®F2) есть двуместная операция, посредством которой из формул F1 и F2 получают новую формулу F=(F1®F2), отражающую сложное высказывание. Значение этого высказывания ложно тогда и только тогда, когда истинно значение F1 и ложно F2.
В программировании для этого используют оператор IMPLIES:
F1 IMPLIES F2 ложно тогда и только тогда, когда F1 истинно, а F2 ложно.
Таблица истинности имеет следующий вид:
|
F1 |
F2 |
F1®F2 |
|
л |
л |
и |
|
л |
и |
и |
|
и |
л |
л |
|
и |
и |
и |
Импликация играет особую роль в математической логике, т.к. многие доказательства представляются в условной форме: “если…, то…”. При этом из истинности посылки (F1) и истинности импликации (F1®F2) следует истинность заключениея F2.
На естественном языке эта операция выражается словами «если …, то … «, «тогда …, когда … «, «постольку …, поскольку … «, «при наличии …, следует … «, » … есть достаточное условие для … «, «… есть необходимое условие для … «, «… при условии, что …» и т. п..
Употребление в повседневной речи слов “если…, то…” несколько отличается от использования их в математической логике. Так в повседневной речи, если высказывание F1 ложно, то сложное высказывание F1®F2 вообще не имеет смысла. В математической логике при ложном высказывании F1 значение сложного высказывания (импликации) всегда истинно.
Пример: Пусть даны высказывания A:=»по проводнику протекает электрический ток» и B — «вокруг проводника есть магнитное поле».
Тогда формула F=A®B отражает высказывание «если по проводнику протекает электрический ток, то вокруг проводника возникает магнитное поле».
Пример: Пусть даны высказывания A:=»на упругое тело оказывают влияние внешние силы» и B:=»в упругом теле возникают внутренние силы, препятствующие изменению формы”. Тогда формула F=(A®B) отражает высказывание «если на упругое тело оказывают влияние внешней силы, то в нем возникают внутренние силы, препятствующие изменению формы»
Эквиваленция (F1«F2) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F=(F1«F2), описывающую сложное высказывание. Значение этого высказывания истинно тогда и только тогда, когда оба операнда F1 и F2 имеют одинаковые значения.
В программировании для этого используют оператор IFF:
F1 IFF F2 истинно тогда и только тогда, когда F1 и F2 имеют одинаковое значение.
Эту операцию наглядно можно изобразить с помощью таблицы истинности.
|
|
F1 |
F2 |
F1«F2 |
|
л |
л |
и |
|
л |
и |
л |
|
и |
л |
л |
|
и |
и |
и |
На естественном языке это выражается словами «для того чтобы…, необходимо и достаточно…», «… лишь при условии…» и т. п..
Пример: Пусть даны высказывания A:=»быть четным числом» и B:=»число делится на два».
Тогда формула F=(A«B) отображает высказывание “для того, чтобы число было четным необходимо и достаточно, чтобы оно делилось на два”.
Пример: Пусть даны высказывания A:=“выполнить загрузку операционной системы в компьютер” и B:=“установить в компьютер дискету с записанной операционной системой“.
Тогда формула F= (A«B) отображает высказывание “для того, чтобы выполнить загрузку операционной системы в компьютер, необходимо и достаточно установить в компьютер дискету с записанной операционной системой»[9].
Пример: Пусть даны высказывания S:=“полная система функций математической логики «, A:=»система функций содержит хотя бы одну нелинейную функцию», B:=»система функций содержит хотя бы одну немонотонную функцию», C:=»система функций содержит хотя бы одну не самодвойственную функцию», D:=»система функций содержит хотя бы одну функцию, не сохраняющую «0» «, E:=»система функций содержит хотя бы одну функцию, не сохраняющую “1“”. Тогда формула F=(S«(A&B&C&D&E)) отражает сложное высказывание “для того чтобы система функций математической логики была полной, необходимо и достаточно, чтобы она содержала хотя бы по одной нелинейную, немонотонную и не самодвойственную функции, а также функции, не сохраняющие “0“ и “1“[9].
Пример: Пусть даны высказывания A:=”урожай будет стабильным ежегодно” и B:=»выполнены все ирригационные работы».
Тогда формула F=(A«B) отображает высказывание «урожай будет ежегодно стабильным тогда и только тогда, когда будут выполнены все ирригационные работы»[10].