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

1. Х Х – закон тождества

 
    

2.   Х  Л – закон противоречия

 
 
    

3.   Х И – закон исключения третьего

 
    

4.  Х – закон двойного отрицания

 
 
    

5. законы коммутативности

 

                

             6.  Х (У Z) (Х У) Z  закон ассоциативности

               Х (У Z) (Х У) Z   закон дистрибутивности 

         7.     законы Де Моргана 

                    8.   законы сочленения переменной с константой

           

    Используя законы логики, можно преобразовывать  формулы.

Пример:  

4. Из множества формул, равносильных между собой, рассмотрим две. Это - совершенная конъюнктивная нормальная форма (СКНФ) и совершенная дизъюнктивная нормальная форма (СДНФ). Они строятся для данной формулы на основе ее таблицы истинности.

           Построение СДНФ:

--  выбираются строки, соответствующие  значениям истинности (1) данной формулы;

-- для каждой выделенной строки составляем конъюнкцию переменных или их отрицаний так, чтобы наборам значений переменных, представленных в строке, соответствовали истинные значения конъюнкции (для этого надо переменные, которые в этой строке принимали значения ложь (0) взять со знаком отрицания, а переменные, принимающие значения истинности (1) без отрицания);

-- составляется дизъюнкция полученных конъюнкций.

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

           Составление СКНФ осуществляется  по следующему алгоритму:

--  выделить те строки таблицы,  в которых формула принимает  значение ложь (0);

-- из переменных, стоящих в каждой такой строке, составить дизъюнкцию, которая должна принимать значения – ложь (0). Для этого все переменные должны войти в нее со значением ложь, следовательно те, которые истинны (1), надо заменить их отрицанием;

--  из полученных дизъюнкций составить конъюнкцию.

    Очевидно, что любая формула, не являющаяся тавтологией, имеет СКНФ.

    СДНФ  и СКНФ используются для получения  следствий из данной формулы.

Пример:  Составить таблицу истинности СДНФ и СКНФ для формулы: .   

СДНФ:  

СКНФ:    

5. Рассмотрим высказывательные форму «Река впадает в Черное море». Она содержит одну переменную и может быть представлена в виде «Река х впадает в Черное море». 

В зависимости  от значений переменной Х  предложение является либо истинным, либо ложным, т.е. задается отображение множества рек на двух элементное множество . Обозначим это отображение , тогда:

Таким образом, имеем функцию, все значения которой принадлежат множеству . 

      Определение: Функция, все значения которой принадлежат множеству , называется предикатом.

Буквы , обозначающие предикаты, называют предикатными символами. 

Предикаты могут задаваться:

1. высказывательной формулой,
2. формулой, т.е. задавая интерпретацию предикатного символа,
3. таблицей.

 

Пример:

1. Р – «впадать в Черное море».

           . Эта формула означает, что «Река а впадает в Черное море».

2. Предикат Р задан высказывательной формулой: «быть простым числом на множестве первых 15 натуральных чисел».
3. В табличной форме предикат имеет вид:

Областью  определения предикатов может быть любое множество.

      Если  предикат при каком-либо наборе входящих переменных теряет смысл, то принято считать, что этому набору соответствует значение Л.

      Если  предикат содержит одну переменную, то его называют одноместным,

две переменные – двуместным,

n переменных – n-местным предикатом. 

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

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

      Определение: Подмножество множества М, на котором задан предикат Р, состоящий из тех и только тех элементов М, которым соответствует значение И предиката Р, называется множеством истинности предиката Р.

Множество истинности обозначается .

      Определение: Отрицанием предиката Р называется предикат, ложный при тех наборах значений переменных, которые обращают Р в истинный, и истинный при тех наборах значений переменных, которые обращают Р в ложный предикат.

Обозначается  отрицание  .

Пример:

- быть студентом АБиК.

- не быть студентом АБиК.

Если  , то множество , где М – множество, на котором заданы предикаты Р и Q . 

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

Пример:

- быть футболистом

- быть студентом

: быть футболистом и быть  студентом. 

      Определение: дизъюнкцией предикатов и называется предикат ложный при тех наборах входящих в него переменных, которые обращают оба предиката в ложные  

Пример:

- быть четным натуральным  числом

- быть нечетным натуральным  числом

: быть натуральным числом.

      Определение: Импликацией предикатов называется предикат, ложный при тех и только тех наборах входящих в него переменных, которые обращают в истинный предикат, а - в ложный.

Обозначается:

Пример:

- быть простым числом на  множестве N

- быть нечетным числом

- ложен при  и истинным при других натуральных числах. 

      Определение: Эквиваленцией предикатов и называется предикат, который становится истинным, если оба предиката и истинны, или оба ложны.

Обозначается:

Пример:

- «выигрывать», т.е. х выигрывает у

- лучше знать шахматную историю,  х знает лучше у

 обозначает, что х выигрывает у у в шахматы тогда и только тогда, когда он лучше знает теорию. 

      Определение: Предикат следует из предиката если импликация истинна при любых входящих в нее значениях переменных.

Обозначаются  следования:  . 

- быть студентом

- ходить в институт

 

Для превращения  предиката в высказывание существуют 2 пути:

1. придание переменной конкретного значения

; х – студент

          Иванов

Иванов  – студент.

2. Навешивание кванторов "- любой, всякий, каждый

                                                                   $ - существует, имеется.

 

Запись " , где обладает свойством Р означает, что всякий предмет х обладает свойством Р. Или по другому, «все х обладают свойством Р».