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

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

Логические операции бывают унарные (или одноместные) и бинарные (или двухместные). Этому отвечает наличие одного или двух операндов у данной операции.

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

Значения логических операций также принадлежат множеству {и; л}.

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

Отрицание (ù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].

 

Логика - доступно для всех