Логические основы информатики

Лекция №3_2

Представление о высказываниях и логических операциях

Алгебра логики

Алгебра логики (алгебра высказываний) и основы математической логики игра­ют важную роль в информатике. Математическая логика присутствует в различ­ных разделах информатики: в виде двоичной логики, на которой основана работа цифровых компьютеров; в виде специальной алгебры логики, лежащей в основе математической модели реляционных баз данных; в виде правил, определяющих функционирование алгоритмов и программ, работу интеллектуальных и эксперт­ных систем. Таким образом, логика для информатики является фундаментальным предметом, изучение которого дает ключ к множеству других разделов.

Представление о высказываниях и логических операциях

Понятие высказывания

Основным понятием математической логики является понятие простого вы­сказывания.

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

Пример. Волга впадает в Каспийское море. Значение высказывания — «истина».

Лондон — столица Франции. Значение высказывания — «ложно».

Карась не рыба. Значение высказывания — «ложно».

Число 6 делится на 2 и на 3. Значение высказывания — «истина».

Если юноша окончил среднюю школу, то он получает аттестат зрелости. Значение высказывания — «истина».

Предложения «Вперед, гардемарины!» или «Какова сейчас температура воздуха за окном?» не являются высказываниями, поскольку не несут в себе однозначных сведений об истинности или ложности. Таким образом, высказыванием обычно являются повествовательные (но не вопросительные и не восклицательные) предложения.

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

Высказывания, которые получаются из элементарных с помощью граммати­ческих связок «не», «и», «или», «если», «то», «тогда и только тогда», принято на­зывать сложными, или составными. В приведенном примере третье высказывание получается из простого высказывания «Карась — рыба» путем добавления отри­цания «не»; четвертое высказывание образовано из элементарных высказываний «Число 6 делится на 2», «Число 6 делится на 3», соединенных союзом «и». Пятое высказывание получается из простых высказываний «Юноша окончил среднюю школу» и «Юноша получает аттестат зрелости» путем добавления грамматической связки «если..., то...». Аналогично, сложные высказывания могут быть получены из простых высказываний путем добавления грамматических связок «или», «тогда и только тогда».

В дальнейшем элементарные высказывания мы будем обозначать малыми бук­вами латинского алфавита; истинное значение высказывания цифрой 1, а ложное значение — цифрой 0. Например, если высказывание а истинно, то будет справед­лива запись а = 1, если высказывание а ложно, то а = 0.

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

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

Соглашения о языке алгебры высказываний

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

Таблица 1. Обозначения в алгебре высказываний

Понятие	Возможные обозначения	Обозначения
Высказывание	Строчные и прописные буквы латинского алфавита: а, Ь, с,..., z, А, В, С,..., Z; прописные буквы русского алфавита: А, Б, В,Я	Строчные буквы латин­ского алфавита: а, Ь, с,..., z
Истинность	Прописная или строчная русская буква И (и); слово истина; прописная или строчная латинская буква Т (t); слово true; цифра 1	Цифра 1
Ложность	Прописная или строчная русская буква Л (л), слово ложь; прописная или строчная латинская буква F (f); слово false, цифра 0	Цифра 0
Отрицание, опровержение, инверсия	Символ Ø, ` или -	Символ надчеркивания `
Конъюнкция, логическое «и»	Символ &, Ù или •. Кроме того, иногда знак между двумя высказываниями просто опускают	Символ Ù
Дизъюнкция, логическое «или»	Символ Ú	Символ Ú
Импликация	Символ É или ®	Символ É
Эквивалентность	Символ ~, «	Символ «
Равносильность	Символ º	Символ º

Логические операции над высказываниями

Над высказываниями можно выполнять следующие логические операции: от­рицание, конъюнкция, дизъюнкция, импликация и эквивалентность.

Операция отрицания высказывания х обозначается х и читается «не х» или «неверно, что х». Таблицы подобного вида принято называть таблицами истинности.

X

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

Пример. Пусть имеется высказывание х «река Волга впадает в Каспийское море». Тогда высказывание «Неверно, что река Волга впадает в Каспийское море» будет отрицанием, то есть х, а высказывание «Неверно, что река Волга не впадает в Ка­спийское море» — двойным отрицанием, то есть f.

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

X	У	хÙу

Пример. Если мы обозначим высказывание «6 делится на 2» как л:, а «6 делится на 3» как у, их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на 3, которое записывается как х Ù у и является истинным.

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

Из определения операции конъюнкции и отрицания ясно, что высказывание хÙ всегда ложно.

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

X	У	х Úу

Пример. Обозначим высказывание «В треугольнике DFE угол D острый» как х, а высказывание «В треугольнике DFE угол Е острый» как у. Тогда дизъюнкция х Ú у этих высказываний «В треугольнике DFE угол D или угол Е острый» ис­тинна, так как обязательно истинно хотя бы одно из высказываний.

В повседневной речи союз «или» употребляется в различном смысле: исклю­чающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.

Из определения операции дизъюнкции и отрицания ясно, что высказывание х v х всегда истинно.

Операция импликации высказываний х и у обозначается символом É, а вы­ражение х É у читается как «если х, то у». Высказывание х называют условием, или посылкой, высказывание у — следствием, или заключением, а высказывание х É у — следованием, или импликацией.

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

X	У	хÉу

Пример. Обозначив высказывание «Число 12 делится на 6» как х, а высказывание «Число 12 делится на 3» как у, мы получим импликацию xÉ у, которая отражает высказывание «Если число 12 делится на 6, то оно делится на 3» и является ис­тинным.

Употребление слов «если..., то...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что если высказыванием ложно, то высказывание «Если х, то у» не имеет смысла. Кроме того, строя предложение «Если х, то y, мы всегда подразумеваем, что предложение у вытекает из предложе­ниях. Употребление слов «если..., то...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.

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

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

X	У	х«у

Пример. Обозначив высказывание «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» как х, а высказывание «В треугольнике SPQ с вершиной S и основанием PQ ÐP = ÐQ» как у, мы можем записать высказывание «Треуголь­ник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда ÐP = ÐQ» в форме эквивалентности х «у. Эквивалентность является ис­тинной, так как высказывания либо одновременно истинны, либо одновременно ложны.

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

Алгебра логики

Понятие формулы алгебры логики

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

(х Ù у) Ú и х É.

Первое высказывание есть дизъюнкция конъюнкции х, у и отрицания выска­зывания z. Второе высказывание есть импликация, посылкой которой является высказывание х, а заключением — отрицание дизъюнкции высказывания у и конъ­юнкции высказываний х, z.

Формулы алгебры логики будем обозначать прописными буквами латинского алфавита А, В, С,.... Буквенные обозначения формул алгебры логики используются в основном в определениях, когда надо обозначить некоторые общие для формул закономерности. Для того чтобы логическими высказываниями, сформулированными на есте­ственном языке, можно было оперировать при помощи алгебры логики, их необ­ходимо формализовать, то есть перевести с естественного языка на язык символов алгебры логики. Для этого рекомендуется следующая процедура:

Если высказывание простое, то ему ставится в соответствие элементарная фор­мула.

Если высказывание составное, то для составления соответствующей формулы нужно:

выделить все элементарные высказывания и логические связки, образующие данное составное высказывание;

заменить их соответствующими символами (различные элементарные вы­сказывания обозначатся различными символами);

расставить скобки в соответствии со смыслом данного высказывания.

Правила записи формулы:

Пример. (х Ù у) Ú º х Ù у Ú — мы опустили скобки, в которые была взята операция дизъюнкции.

х É º х É — мы опустили скобки, в которые было заключена формула со знаком отрицания над ней.

Логическое значение формулы алгебры логики полностью определяется ре­зультатом логических операций над значениями входящих в нее элементарных высказываний. Например, логическим значением формулы в случае, если х=1,y=1, z = 0, будет истина, то есть = 1.

Таблица истинности позволяет полностью описать все возможные значения любой формулы в зависимости от значений входящих в нее элементарных вы­сказываний. Очевидно, что если в формуле п элементарных высказываний, то она принимает 2n значений, состоящих из нулей и единиц, и результирующая таблица содержит 2n строк.

Для формулы таблица истинности имеет вид

x	y			Úу	xÚ	ÚуÉ xÚ

Дата добавления: 2014-01-03