1.1 алгебра высказыванийМножество пропозициональных переменных T={A, B, C,…} с заданными над ним логическими операциями F={ù; &; Ú; ®; « } формируют алгебру высказываний, т.е. Aв=<T; F;> Символы логических операций заданы логическими связками: ù - отрицание, & - конъюнкция, Ú - дизъюнкция, ® - импликация, « - эквиваленция. Всякое сложное высказывание, которое может быть получено из элементарных высказываний посредством применения логических связок отрицания, коньюнкции, дизьюнкции, импликации и эквиваленции, называют формулой алгебры логики. Любую пропозициональную переменную можно назвать формулой нулевого порядка, т. е. Ai =Fi. Если F1 и F2 – пропозициональные формулы, то ùF1; ùF2; F1&F2; F1ÚF2; F1®F2 и F1«F2 также пропозициональные формулы. Никаких других формул в исчислении высказываний нет. Множество формул образуют язык математической логики. Это множество перечислимо и разрешимо. Для формирования сложных формул используют вспомогательные символы “(“ и “)”.
1.1.1 Логические операции Логическая связка указывает на необходимость исполнения логической операции над пропозициональными переменными или формулами, окружающими логическую связку. Логические операции бывают унарные (или одноместные) и бинарные (или двухместные). Этому отвечает наличие одного или двух операндов у данной операции. Значение формулы полностью определяется значениями входящих в нее пропозициональных переменных. Значения логических операций также принадлежат множеству {и; л}. Все значения логической формулы в зависимости от значений входящих в нее элементарных высказываний, могут быть полностью описаны с помощью таблицы истинности. Отрицание (ù F) есть одноместная операция, посредством которой ее значение есть отрицание значения операнда. В программировании для этого используют оператор NOT: NOT 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.
Из определения операций коньюнкции и отрицания очевидно, что (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.
Из определения операций дизьюнкции и отрицания очевидно, что (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) и истинности импликации (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 имеют одинаковое значение. Эту операцию наглядно можно изобразить с помощью таблицы истинности.
На естественном языке это выражается словами "для того чтобы…, необходимо и достаточно…", "… лишь при условии..." и т. п.. Пример: Пусть даны высказывания A:="быть четным числом" и B:="число делится на два". Тогда формула F=(A«B) отображает высказывание “для того, чтобы число было четным необходимо и достаточно, чтобы оно делилось на два”. Пример: Пусть даны высказывания A:=“выполнить загрузку операционной системы в kомпьютер” и 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].
1.1.2 Правила записи сложных формул Для определения истинности сложного суждения необходимо анализировать значение истинности каждого составного высказывания и формировать последовательно значение истинности каждой подформулы, входящей в формулу сложного суждения. Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее пропозициональных переменных. Все возможные логические значения формулы в зависимости от значений входящих в нее элементарных высказываний, могут быть полностью описаны с помощью таблицы истинности. Пример: Суждение "если инвестиции на текущий год не изменятся (A), то возрастет расходная часть бюджета (B) или возникнет безработица (C), а если возрастет расходная часть бюджета, то налоги не будут снижены (D) и, наконец, если налоги не будут снижены и инвестиции не изменятся, то безработица не возникнет" [10 ]. В этом суждении есть четыре повествовательных предложения, которые следует заместить пропозициональными переменными и формально описать суждение. Тогда формула сложного суждения имеет вид: F =(A®(BÚC))&(B®D)&((D&A)® ùC). Для различных значений истинности пропозициональных переменных и подформул, построенных на логических связках, можно последовательно определить значение истинности формулы F. Таблица, в которой рассматриваются любые наборы пропозициональных переменных и определяются значения всех подформул формулы, называют таблицей истинности. Ниже представлена таблица истинности для этого суждения.
|