Относительно понятий и отношений между ними можно высказывать различные суждения. Языковой формой суждений являются повествовательные предложения. Предложения, используемые в математике, могут быть записаны как в словесной форме, так и в символической. Предложения могут нести верную или ложную информацию.
Высказыванием называется любое повествовательное предложение, которое может быть либо истинным, либо ложным.
Пример . Следующие предложения являются высказываниями:
1) Все студенты МГПУ – отличники (ложное высказывание),
2) На Кольском полуострове водятся крокодилы (ложное высказывание),
3) Диагонали прямоугольника равны (истинное высказывание),
4) Уравнение не имеет действительных корней (истинное высказывание),
5) Число 21 – четное (ложное высказывание).
Следующие предложения не являются высказываниями:
Какая погода будет завтра?
х – натуральное число,
745 + 231 – 64.
Высказывания принято обозначать большими буквами латинского алфавита: А, В, С,…, Z .
«Истина» и «ложь» называются значениями истинности высказывания . Каждое высказывание либо истинно, либо ложно, одновременно быть и тем, и другим, оно не может.
Запись [ А ] = 1 означает, что высказываниеА – истинно .
А запись [ А ] = 0 означает, что высказываниеА – ложно .
Предложение
не является высказыванием, так как о
нем невозможно сказать: истинно оно или
ложно. При подстановке конкретных
значений переменнойх
оно обращается в высказывание: истинное
или ложное.
Пример
.
Если
,
то
– ложное высказывание, а если
,
то
– истинное высказывание.
Предложение
называетсяпредикатом
или высказывательной
формой
. Оно
порождает множество высказываний одной
и той же формы.
Предикатом называется предложение с одной или несколькими переменными, обращающееся в высказывание всякий раз при подстановке вместо переменных их значений.
В зависимости от числа переменных, входящих в предложение, различают одноместные, двухместные, трехместные и т.д. предикаты, которые обозначаются: и т.д.
Пример
.
1)
– одноместный предикат,
2) «Прямая х перпендикулярна прямой у » – двухместный предикат.
Также в предикатах переменные могут содержаться неявно. В предложениях: «Число четное», «две прямые пересекаются» переменных нет, но они подразумеваются: «Число х – четное», «две прямые х и у пересекаются».
При задании предиката указывают его область определения – множество, из которого выбираются значения переменных, входящих в предикат.
Пример
.
Неравенство
можно рассматривать на множестве
натуральных чисел, а можно считать, что
значение переменной выбирается из
множества действительных чисел. В первом
случае областью определения неравенства
будет множество натуральных чисел, а
во втором – множество действительных
чисел.
Одноместным предикатом , заданным на множестве Х , называется предложение с переменной, которое обращается в высказывание при подстановке в него переменной из множества Х .
Множеством истинности одноместного предиката называется множество тех значений переменной из области ее определения, при подстановке которых предикат обращается в истинное высказывание.
Пример
.
Множеством истинности предиката
,
заданном на множестве действительных
чисел, будет промежуток
.
Множество истинности предиката
,
заданном на множестве целых неотрицательных
чисел, состоит из одного числа 2.
Множество
истинности
двухместного предиката
состоит из всех таких пар
при подстановке которых в этот предикат
получается истинное высказывание.
Пример
.
Пара
принадлежит множеству истинности
предиката
,
т.к.
– истинное высказывание, а пара
не принадлежит, т.к.
– ложное высказывание.
Высказывания и предикаты могут быть как простыми, так и сложными (составными). Сложные предложения образуются из простых с помощью логических связок – слов «и », «или », «если…, то … », «тогда и только тогда, когда… ». С помощью частицы «не » или словосочетания «неверно, что » можно из данного предложения получить новое. Предложения, не являющиеся составными, называют элементарными .
Примеры . Составные предложения:
Число 42 – четное и делится на 7. Образовано из двух элементарных предложений: Число 42 четное, число 42 делится на 7 и составлено с помощью логической связки «и ».
Число х больше или равно 5. Образовано из двух элементарных предложений: Число х больше 5 и число х равно 5 и составлено с помощью логической связки «или ».
Число 42 не делится на 5. Образовано из предложения: Число 42 делится на 5 с помощью частицы «не ».
Значение истинности элементарного высказывания определяют, исходя из его содержания с опорой на известные знания. Чтобы определить значение истинности составного высказывания, надо знать смысл логических связок, с помощью которых оно образовано из элементарных, и уметь выявлять логическую структуру высказывания.
Пример . Выявим логическую структуру предложения: «Если углы вертикальны, то они равны». Оно состоит из двух элементарных предложений: А – углы вертикальные, В – углы равны. Соединены они в одно составное предложение с помощью логической связки «если…, то… ». Данное составное предложение имеет логическую структуру (форму): «если А, то В ».
Выражение
«для любого х
»
или «для всех х
»
или «для каждого х
»
называется квантором
общности
и обозначается
.
при помощи квантора общности, обозначается:
и читается: «Для любого значениях
из множества Х
имеет место
».
Выражение
«существует х
»
или «для некоторых х
»
или «найдется такое х
»
называется квантором
существования
и
обозначается
.
Высказывание,
полученное из высказывания или предиката
при помощи квантора существования,
обозначается:
и читается: «Для некоторыхх
из множества Х
имеет место
»
или «Существует (найдется) такое значениех
из Х
,
что имеет место
».
Кванторы общности и существования употребляются не только в математических выражениях, но и в повседневной речи.
Пример . Следующие высказывания содержат квантор общности:
а) Все стороны квадрата равны; б) Каждое целое число является действительным; в) В любом треугольнике медианы пересекаются в одной точке; г) У всех студентов есть зачетная книжка.
Следующие высказывания содержат квантор существования:
а)
Существуют числа, кратные 5; б) Найдется
такое натуральное число
,
что
;
в) В некоторых студенческих группах
учатся кандидаты в мастера спорта; г)
Хотя бы один угол в треугольнике острый.
Высказывание
являетсяистинным
–
тождество, т.е. принимает истинные
значения при подстановке в него любых
значений переменной.
Пример
.
Высказывание
истинно.
Высказывание
ложно
,
если при некотором значении переменной
х
предикат
Пример
.
Высказывание
ложно, т.к. при
предикат
превращается в ложное высказывание.
Высказывание
являетсяистинным
тогда и только тогда, когда предикат
не является тождественно ложным, т.е.
при некотором значении переменнойх
предикат
Пример
.
Высказывание
истинно, т.к. при
предикат
превращается в истинное высказывание.
Высказывание
ложно
,
если предикат
является противоречием, т.е. тождественно
ложным высказыванием.
Пример
.
Высказывание
ложно, т.к. предикат
является тождественно ложным.
Пусть
предложение А
–
высказывание.
Если перед сказуемым данного
предложения поставить частицу «не
»
либо перед всем предложением поставить
слова «неверно,
что
»,
то получится новое предложение, которое
называется отрицанием
данного
и обозначается:
А
или
(читают:
«не
А»
или
«неверно,
что
А
»).
|
Отрицанием
высказывания А
называется
высказывание
Таблица истинности отрицания: |
|
или
А
,
которое ложно, когда высказывание А
истинно, и истинно, когда
высказывание А
– ложно.
Пример . Если высказывание А : «Вертикальные углы равны», то отрицание этого высказывания А : «Вертикальные углы не равны». Первое из этих высказываний истинное, а второе – ложное.
Для построения отрицания высказываний с кванторами надо:
квантор общности заменить квантором существования или наоборот;
высказывание заменить его отрицанием (поставить перед глаголом частицу «не »).
На языке математических символов это запишется так.
Тема программы: Высказывания и операции над ними.
Цели урока:
1) Обобщить теоретические знания по теме: «Высказывания и операции над ними».
2) Рассмотреть алгоритмы решений заданий теме «Высказывания и операции над ними», решить задачи.
3) Формировать умение прогнозировать собственную деятельность, умение организовать свою деятельность и анализировать ее.
Время выполнения: 1 час.
Теоретические основы
Основным понятием математической логики является понятие «простого высказывания». Под высказыванием обычно понимают всякое повествовательное предложение, утверждающее что-либо о чем-либо, и при этом мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь».
Примеры высказываний.
1) Москва стоит на Неве.
2) Лондон - столица Англии.
3) Сокол не рыба.
4) Число 6 делится на 2 и на 3.
Высказывания 2), 3), 4) истинны, а высказывание 1) ложно.
Очевидно, предложение «Да здравствует Россия!» не является высказыванием.
Различают два вида высказываний.
Высказывание, представляющее собой одно утверждение, принято называть простым или элементарным. Примерами элементарных высказываний могут служить высказывания 1) и 2).
Высказывания, которые получаются из элементарных с помощью грамматических связок «не», «и», «или», «если.... то...», «тогда и только тогда», принято называть сложными или составными.
Так, высказывание 3) получается из простого высказывания «Сокол - рыба» с помощью отрицания «не», высказывание 4) образовано из элементарных высказываний «Число 6 делится на 2», «Число 6 делится на З», соединенных союзом «и».
Аналогично сложные высказывания могут быть получены из простых высказываний с помощью грамматических связок «или», «тогда и только тогда».
В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, а от их житейского содержания отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.
Элементарные высказывания обозначаются малыми буквами латинского алфавита: х, у, z, ..., а, b, с, ...;
истинное значение высказывания цифрой 1, а ложное значение - буквой цифрой 0.
Если высказывание а
истинно, то будем писать а = 1
, а если а
ложно, то а = 0
.
Логические операции над высказываниями
Отрицание.
Отрицанием высказывания х называется новое высказывание , которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно.
Отрицание высказывания х обозначается и читается «не х» или «неверно, что х» .
Логические значения высказывания можно описать с помощью таблицы.
Таблицы такого вида принято называть таблицами истинности.
Пусть х
высказывание. Так как также является высказыванием, то можно образовать отрицание высказывания , то есть высказывание , которое называется двойным отрицанием высказывания х
. Ясно, что логические значения высказываний х
и совпадают.
Например, для высказывания «Путин президент России» отрицанием будет высказывание «Путин не президент России», а двойным отрицанием будет высказывание «Неверно, что Путин не президент России».
Конъюнкция.
Конъюнкцией (логическим умножением) двух высказываний х и у
называется новое высказывание, которое считается истинным, если оба высказывания х и у
истинны, и ложным, если хотя бы одно из них ложно.
Конъюнкция высказываний х и у
обозначается символом х&у ( , ху)
, читается «х и у»
. Высказывания х и у
называются членами конъюнкции.
Логические значения конъюнкции описываются следующей таблицей истинности:
Например, для высказываний «6 делится на 2», «6 делится на 3» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на 3», которое, очевидно, истинно.
Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания далеких друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний.
Дизъюнкция
Дизъюнкцией (логическим сложением) двух высказываний х и у
называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний х, у
истинно, и ложным, если они оба ложны. Дизъюнкция высказываний х, у
обозначается символом «x V у»
, читается «х или у»
. Высказывания х, у
называются членами дизъюнкции.
Логические значения дизъюнкции описываются следующей таблицей истинности:
В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.
Импликация.
Импликацией двух высказываний х и у
называется новое высказывание, которое считается ложным, если х истинно, а у - ложно, и истинным во всех остальных случаях.
Импликация высказываний х, у
обозначается символом
, читается«если х, то у» или «из х следует у».
Высказывание х
называют условием или посылкой, высказывание у
- следствием или заключением, высказывание
следованием или импликацией.
Логические значения операции импликации описываются следующей таблицей истинности:
Употребление слов «если.... то...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание х
ложно, то высказывание «Если х, то у»
вообще не имеет смысла. Кроме того, строя предложение вида «если х, то у»
в обыденной речи, мы всегда подразумеваем, что предложение у
вытекает из предложения х
. Употребление слов «если..., то...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.
Импликация играет важную роль в математических доказательствах, так как многие теоремы формулируются в условной форме «Если х, то у».
Если при этом известно, что х
истинно и доказана истинность импликации
, то мы вправе сделать вывод об истинности заключения у
.
Эквивалентность.
Эквивалентностью двух высказываний х и у называется новое высказывание, которое считается истинным, когда оба высказывания х, у либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.
Эквивалентность высказываний х, у
обозначается символом , читается«для того, чтобы х, необходимо и достаточно, чтобы у» или «х тогда и только тогда, когда у».
Высказывания х, у
называются членами эквивалентности.
Логические значения операции эквивалентности описываются следующей таблицей истинности:
Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.
Практические задания
1. Установить логическую структуру следующих предложений и записать их на языке логики высказываний:
- Если металл нагревается, он плавится.
- Неправда, что философские споры неразрешимы.
- Деньги - продукт стихийного развития товарных отношений, а не результат договоренности или какого-либо иного сознательного акта.
2. Записать логической формулой следующие высказывания:
а) если на улице дождь, то нужно взять с собой зонт или остаться дома;
Б) если - прямоугольный и стороны - равны, то
3. Проверить истинность высказывания:
а) , если, .
б) , если, .
в) , если, .
4. Проверить истинность высказывания:
а) Чтобы завтра пойти на занятия, я должен встать рано. Если я сегодня пойду в кино, то лягу спать поздно. Если я лягу спать поздно, то встану поздно. Следовательно, либо я не пойду в кино, либо не пойду на занятия.
б) Я пойду либо в кино, либо в бассейн. Если я пойду в кино, то получу эстетическое удовольствие. Если я пойду в бассейн, то получу физическое удовольствие. Следовательно, если я получу физическое удовольствие, то не получу эстетического удовольствия.
5 . На вопрос: «Кто из трех студентов изучал дискретную математику?» получен верный ответ: «Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий». Кто изучал дискретную математику?
6. Определите, кто из четырех студентов сдал экзамен, если известно:
если первый сдал, то и второй сдал;
если второй сдал, то третий сдал или первый не сдал;
если четвертый не сдал, то первый сдал, а третий не сдал;
если четвертый сдал, то и первый сдал.
Контрольные вопросы
1. Какие элементы входят язык логики?
2. Какие способы установления общезначимости формулы логики вы знаете?
Список литературы
Практические занятия № 10-11
Тема программы: Формулы алгебры высказываний.
Среди суждений, устанавливающих различные отношения между математическими понятиями, выделяют высказывания и высказывательные формы.
Высказыванием называется предложение,
относительно которого
имеет смысл вопрос, истинно оно или ложно. .
Например, предложение «Число 6 четное» есть истинное высказывание, а предложение «2 + 4 = З 2 » -ложное высказывание.
В математике различают элементарное и составное
высказывание.
Предложение «Число 28 делится на 7» элементарное. Составными
высказываниями являются, например, следующие:
1. число 28 четное и делится на 7;
2.число х меньше или равно 8;
3. если треугольник равнобедренный, то углы в нем при основании равны. Составные высказывания образуются из элементарных с помощью слов «и» («А и В»), «или» («И или В»), частицы «не» (не А) и некоторых других. Эти слова в математике называют логическими связками.
Вообще каждому высказыванию приписывают одно из двух значений И (истина), если оно истинно, и Л (ложь), если оно ложно. Значения И и Л называют значениями истинности высказывания. Если высказывание элементарное, то его значение истинности определяют по содержанию, опираясь на известные знания. А как быть, если высказывание составное? Как определить значение истинности такого высказывания? Здесь на помощь приходит форма высказывания.
Конъюнкцией двух высказываний А и В называют высказывание вида А и В, истинное, если оба высказывания истинны, и ложное, если хотя бы одно из них ложное.
Пример. Установим, истинно или ложно высказывание: 1). число 102 четное и делится на 9.
В этом случае составное высказывание имеет форму «А и В», где А - «Число 102 четное», а В - «Число 102 делится на 9». Легко видеть, что высказывание А истинное, а высказывание В ложное (число 102 не делится на 9, так как на 9 не делится сумма цифр в записи этого числа). Следовательно, и все предложение ложное.
Дезъюнкцией двух высказываний А или В называют высказывание вида А или В, ложное, если оба высказывания ложные и истинное во всех остальных случаях.
Пример. Установим, истинны ли высказывания: число 102 четное или делится на 3.
В этом случае составное высказывание имеет форму «А или В», где А -«Число 102 четное», В - «Число 102 делится на 3»
Видим, что высказывания А или В истинны, следовательно, данное высказывание истинно.
Импликацией двух высказываний АиВгазывается высказывание вида А=>В (если А то В), ложное только в одном случае, если А истинное, а В -ложное, во всех остальных случаях оно истинное.
Отрицанием высказывания А называется высказывание вида А, которое истинно, если высказывание А ложно, и ложно, когда А истинно.
Свойства
Рассмотрим несколько свойств декартова произведения:
1. Если A ,B - конечные множества, то A ×B - конечное. И наоборот, если одно из множеств-сомножителей бесконечное, то и результат их произведения - бесконечное множество.
2. Количество элементов в декартовом произведении равно произведению чисел элементов множеств-сомножителей (в случае их конечности, разумеется): |A ×B |=|A |⋅|B | .
3. A np ≠(A n ) p - в первом случае целесообразно рассмотреть результат декартова произведения как матрицу размеров 1×np , во втором же - как матрицу размеров n ×p .
4. Коммутативный закон не выполняется, т.к. пары элементов результата декартова произведения упорядочены: A ×B ≠B ×A .
5. Ассоциативный закон не выполняется: (A ×B )×C ≠A ×(B ×C ) .
6. Имеет место дистрибутивность относительно основных операциях на множествах: (A ∗B )×C =(A ×C )∗(B ×C ),∗∈{∩,∪,∖}
11. Понятие высказывания. Элементарные и составные высказывания.
Высказывание - это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно (И-1) или ложно (Л-0), но не то и другое одновременно.
Например, «Сегодня идет дождь», «Иванов выполнил лабораторную работу №2 по физике».
Если у нас имеется несколько исходных высказываний, то из них при помощи логических союзов или частиц мы можем образовывать новые высказывания, истинностное значение которых зависит только от истинностных значений исходных высказываний и от конкретных союзов и частиц, которые участвуют в построении нового высказывания. Слова и выражения «и», «или», «не», «если... , то», «поэтому», «тогда и только тогда» являются примерами таких союзов. Исходные высказывания называются простыми , а построенные из них с помощью тех или иных логических союзов новые высказывания - составными . Разумеется, слово «простые» никак не связано с сутью или структурой исходных высказываний, которые сами могут быть весьма сложными. В данном контексте слово «простой» является синонимом слова «исход-ный». Важно то, что значения истинности простых высказываний предполагаются известными или заданными; в любом случае они никак не обсуждаются.
Хотя высказывание типа «Сегодня не четверг» не составлено из двух различных простых высказываний, для единообразия конструкции оно также рассматривается как составное, по-скольку его истинностное значение определяется истинностным значением другого высказыва-ния «Сегодня четверг»
Пример 2. Cледующие высказывания рассматриваются как составные:
Я читаю «Московский комсомолец» и я читаю «Коммерсант».
Если он сказал это, значит, это верно.
Солнце не является звездой.
Если будет солнечно и температура превысит 25 0 , я приеду поездом или автомобилем
Простые высказывания, входящие в составные, сами по себе могут быть совершенно произвольными. В частности, они сами могут быть составными. Описываемые ниже базисные типы составных высказываний определяются независимо от образующих их простых высказываний.
12. Операции над высказываниями.
1. Операция отрицания.
Отрицанием высказывания А (читается «не А », «неверно, что А »), которое истинно, когда А ложно и ложно, когда А – истинно.
Отрицающие друг друга высказывания А и называются противоположными.
2. Операция конъюнкции .
Конъюнкцией высказываний А и В называется высказывание, обозначаемое А В (читается «А и В »), истинные значения которого определяются в том и только том случае, когда оба высказывания А и В истинны.
Конъюнкцию высказываний называют логическим произведением и часто обозначают АВ.
Пусть дано высказывание А – «в марте температура воздуха от 0 С до +7 С » и высказывание В – «в Витебске идет дождь». Тогда А В будет следующей: «в марте температура воздуха от 0 С до +7 С и в Витебске идет дождь». Данная конъюнкция будет истинной, если будут высказывания А и В истинными. Если же окажется, что температура была меньше 0 С или в Витебске не было дождя, то А В будет ложной.
3 . Операция дизъюнкции .
Дизъюнкцией высказываний А и В называется высказывание А В (А или В ), которое истинно тогда и только тогда, когда хотя бы одно из высказываний истинно и ложно – когда оба высказывания ложны.
Дизъюнкцию высказываний называют также логической суммой А+В.
Высказывание «4<5 или 4=5 » является истинным. Так как высказывание «4<5 » – истинное, а высказывание «4=5 » – ложное, то А В представляет собой истинное высказывание «4 5 ».
4 . Операция импликации .
Импликацией высказываний А и В называется высказывание А В («если А , то В », «из А следует В »), значение которого ложно тогда и только тогда, когда А истинно, а В ложно.
В импликации А В высказывание А называют основанием, или посылкой, а высказывание В – следствием, или заключением.
13. Таблицы истинности высказываний.
Таблица истинности - это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию и значениями функции.
Таблицы истинности применяются для:
Вычисления истинности сложных высказываний;
Установления эквивалентности высказываний;
Определения тавтологий.
Установление истинности сложных высказываний.
Пример 1. Установить истинность высказывания · С
Решение.
В состав сложного высказывания входят 3 простых высказывания: А, В, С. В таблице заполняются колонки значениями (0, 1). Указываются все возможные ситуации. Простые высказывания от сложных отделяются двойной вертикальной чертой.
При составлении таблицы надо следить за тем, чтобы не перепутать порядок действий; заполняя столбцы, следует двигаться “изнутри наружу”, т.е. от элементарных формул к более и более сложным; столбец, заполняемый последним, содержит значения исходной формулы.
| А | В | С | А+ | · С | ||
Из таблицы видно, что данное высказывание истинно только в случае, когда А=0, В=1, С=1. Во всех остальных случаях оно ложно.
14. Равносильные формулы.
Две формулы А и В называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулу элементарных высказываний.
Равносильность обозначается знаком « ». Для преобразования формул в равносильные важную роль играют основные равносильности, выражающие одни логические операции через другие, равносильности, выражающие основные законы алгебры логики.
Для любых формул А , В , С справедливы равносильности.
I. Основные равносильности
закон идемпотентности
1-истина
0-ложь
Закон противоречия
Закон исключенного третьего
закон поглощения
формулы расщепления
закон склеивания
II. Равносильности, выражающие одни логические операции через другие.
закон де Моргана
III. Равносильности, выражающие основные законы алгебры логики.
коммутативный закон
ассоциативный закон
дистрибутивный закон
15. Формулы логики высказываний.
Виды формул классической логики высказываний – в логике высказываний различают следующие виды формул:
1. Законы (тождественно-истинные формулы) – формулы, которые при любых интерпретациях пропозициональных переменных принимают значение «истинно» ;
2. Противоречия (тождественно-ложные формулы) – формулы, которые при любых интерпретациях пропозициональных переменных принимают значение «ложно» ;
3. Выполнимые формулы – такие, которые принимают значение «истинно» хотя бы при одном наборе значений истинности входящих в их состав пропозициональных переменных.
Основные законы классической логики высказываний:
1. Закон тождества: ;
2. Закон противоречия:
;
3. Закон исключенного третьего: ;
4. Законы коммутативности и : , ;
5. Законы дистрибутивности относительно ,и наоборот: , ;
6. Закон удаления истинного члена конъюнкции: ;
7. Закон удаления ложного члена дизъюнкции: ;
8. Закон контрапозиции: ;
9. Законы взаимовыразимости пропозициональных связок: , , , , , .
Процедура разрешимости – метод, позволяющий для каждой формулы установить является она законом, противоречием или выполнимой формулой. Самой распространенной процедурой разрешимости является метод истинностных таблиц. Однако он не единственный. Эффективным методом разрешимости является метод нормальных форм для формул логики высказываний. Нормальной формой формулы логики высказываний является форма, не содержащая знака импликации « ». Различают конъюнктивную и дизъюнктивную нормальные формы. Конъюнктивная форма содержит только знаки конъюнкции « ». Если в формуле, приведенной к конъюнктивной нормальной форме, встречается подформула вида , то вся формула в этом случае является противоречием . Дизъюнктивная форма содержит только знаки дизъюнкции « ». Если в формуле, приведенной к дизъюнктивной нормальной форме, встречается подформула вида , то вся формула в этом случае является законом . Во всех остальных случаях формула является выполнимой формулой .
16. Предикаты и операции над ними. Кванторы.
Предложение, содержащее одну или несколько переменных и которое при конкретных значениях переменных является высказыванием, называется высказывательной формой или предикатом.
В зависимости от числа переменных, входящих в предложение, различают одноместные, двухместные, трехместные и т.д. предикаты, обозначаемые соответственно: А(х ), В(х , у ), С(х , у , z ).
Если задан некоторый предикат, то с ним связаны два множества:
1. Множество (область) определения Х , состоящее из всех значений переменных, при подстановке которых в предикат последний обращается в высказывание. При задании предиката обычно указывают его область определения.
2. Множество истинности Т, состоящее из всех тех значений переменных, при подстановке которых в предикат получается истинное высказывание.
Множество истинности предиката всегда является подмножеством его области определения, то есть .
Над предикатами можно совершать те же операции, что и над высказываниями.
1. Отрицанием предиката А(х ), заданного на множестве Х, называется предикат , истинный при тех значениях , при которых предикат А(х ) обращается в ложное высказывание, и наоборот.
Из данного определения следует, что предикаты А(х ) и В(х ) не являются отрицаниями друг друга, если найдется хотя бы одно значение , при котором предикаты А(х ) и В(х ) обращаются в высказывания с одинаковыми значениями истинности.
Множество истинности предиката является дополнением к множеству истинности предиката А(х ). Обозначим через Т А множество истинности предиката А(х ), а через Т - множество истинности предиката . Тогда .
2. Конъюнкцией предикатов А(х ) и В(х х ) В(х х Х, при которых оба предиката обращаются в истинные высказывания.
Множество истинности конъюнкции предикатов есть пересечение множеств истинности предиката А(х
) В(х
). Если обозначить множество истинности предиката А(х) через Т А, а множество истинности предиката В(х) через Т В и множество истинности предиката А(х) В(х) через , то 
3. Дизъюнкцией предикатов А(х) и В(х ), заданных на множестве Х, называется предикат А(х ) В(х ), обращающийся в истинное высказывание при тех и только тех значениях х Х, при которых хотя бы один из предикатов обратился в истинное высказывание.
Множество истинности дизъюнкции предикатов есть объединение множеств истинности образующих ее предикатов, т.е. .
4.Импликацией предикатов А(х ) и В(х ), заданных на множестве Х, называется предикат А(х ) В(х ), который ложен при тех и только тех значениях переменной, при которых первый предикат обращается в истинное высказывание, а второй – в ложное.
Множество истинности импликации предикатов есть объединение множества истинности предиката В(х
) с дополнением к множеству истинности предиката А(х
), т.е.
5. Эквиваленцией предикатов А(х ) и В(х ), заданных на множестве Х, называется предикат , который обращается в истинное высказывание при всех тех и только тех значениях переменной, при которых оба предиката обращаются либо в истинные высказывания, либо в ложные высказывания.
Множество истинности эквиваленции предикатов есть пересечение множества истинности предиката с множеством истинности предиката .
Кванторные операции над предикатами
Предикат можно перевести в высказывание способом подстановки и способом «навешивание квантора».
Про числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 можно сказать: а) все данные числа простые; б) некоторые из данных чисел четные.
Так как относительно этих предложений можно сказать, что они истинны или ложны, то полученные предложения – высказывания.
Если из предложения «а» убрать слово «все», а из предложения «б» - слово «некоторые», то получим следующие предикаты: «данные числа простые», «данные числа нечетные».
Слова «все» и «некоторые» называются кванторами. Слово «квантор» латинского происхождения и означает «сколько», т. е. квантор показывает, о скольких (всех или некоторых) объектах говорится в том или ином предложении.
Различают два основных вида кванторов: квантор общности и квантор существования.
Термины «всякий», «любой», «каждый» носят название – квантор всеобщности. Обозначается .
Пусть А(х ) – определенный предикат, заданный на множестве Х. Под выражением А(х ) будем понимать высказывание истинное, когда А(х ) истинно для каждого элемента из множества Х, и ложное в противном случае.R .
В примере 1 для R 1 область определения: , множество значений - . Для R 2 область определения: , множество значений: .
Во многих случаях удобно использовать графическое изображение бинарного отношения. Оно осуществляется двумя способами: с помощью точек на плоскости и с помощью стрелок.
В первом случае выбирают две взаимно перпендикулярные линии в качестве горизонтальной и вертикальной осей. На горизонтальной оси откладывают элементы множества A и через каждую точку проводят вертикальную линию. На вертикальной оси откладывают элементы множества B , через каждую точку проводят горизонтальную линию. Точки пересечения горизонтальных и вертикальных линий изображают элементы прямого произведения
18. Способы задания бинарных отношений.
Всякое подмножество декартова произведения A×B называется бинарным отношением, определенным на паре множеств A и B (по латыни «бис» обозначает «дважды»). В общем случае по аналогии с бинарными можно рассматривать и n-арные отношения как упорядоченные последовательностиn элементов, взятых по одному из n множеств.
Для обозначения бинарного отношения применяют знак R. Поскольку R- это подмножество множества A×B, то можно записать R⊆A×. Если же требуется указать, что (a, b) ∈ R, т. е. между элементами a ∈ A и b ∈ B существует отношение R, то пишут aRb.
Способы задания бинарных отношений:
1. Это использование правила, согласно которому указываются все элементы, входящие в данное отношение. Вместо правила можно привести список элементов заданного отношения путем непосредственного их перечисления;
2. Табличный, в виде графов и с помощью сечений. Основу табличного способа составляет прямоугольная система координат, где по одной оси откладываются элементы одного множества, по второй - другого. Пересечения координат образуют точки, обозначающие элементы декартова произведения.
На (рисунке 1.16) изображена координатная сетка для множеств. Точкам пересечения трех вертикальных линий с шестью горизонтальными соответствуют элементы множества A×B. Кружочками на сетке отмечены элементы отношения aRb, где a ∈ A и b ∈ B, R обозначает отношение «делит».
Бинарные отношения задаются двухмерными системами координат. Очевидно, что все элементы декартова произведения трех множеств аналогично могут быть представлены в трехмерной системе координат, четырех множеств- в четырехмерной системе и т. д;
3. Способ задания отношений с помощью сечений используется реже, поэтому рассматривать его не будем.
19. Рефлексивность бинарного отношения. Пример.
В математике бинарное отношение на множестве называется рефлексивным, если всякий элемент этого множества находится в отношении с самим собой.
Свойство рефлексивности при заданных отношениях матрицей характеризуется тем, что все диагональные элементы матрицы равняются 1; при заданных отношениях графом каждый элемент имеет петлю - дугу (х, х).
Если это условие не выполнено ни для какого элемента множества, то отношение называется антирефлексивным.
Если антирефлексивное отношение задано матрицей, то все диагональные элементы являются нулевыми. При задании такого отношения графом каждая вершина не имеет петли - нет дуг вида (х, х).
Формально антирефлексивность отношения определяется как: .
Если условие рефлексивности выполнено не для всех элементов множества, говорят, что отношение нерефлексивно.
©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-12
Пример 1. Установить истинность высказывания · С Решение. В состав сложного высказывания входят 3 простых высказывания: А, В, С.
В таблице заполняются колонки значениями (0, 1). Указываются все возможные ситуации. Простые высказывания от сложных отделяются двойной вертикальной чертой. При составлении таблицы надо следить за тем, чтобы не перепутать порядок действий; заполняя столбцы, следует двигаться “изнутри наружу”, т.е. от элементарных формул к более и более сложным; столбец, заполняемый последним, содержит значения исходной формулы.
| А | В | С | А+ | · С | ||
| 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 |
Из таблицы видно, что данное высказывание истинно только в случае, когда А=0, В=1, С=1. Во всех остальных случаях оно ложно.
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:
Еще по теме 1. Установление истинности сложных высказываний.:
- 29. Проблема разрешимости в алгебре высказываний(АВ). Алгоритмы проверки формул алгебры высказываний на тождественную истинность: составление таблицы истинности, выполнение равносильных преобразований (анализ КНФ), алгоритм редукции, алгоритм Квайна. Преимущества и недостатки указанных методов.
- Вопрос 6. Исчисление высказываний. Аксиомы. Правило вывода. Вывод. Тождественная истинность выводимых формул (доказать). Непротиворечивость исчисления высказываний. Теорема о полноте исчисления высказываний. Проблема разрешимости. Исчисление высказываний. Проблема разрешимости