Логические операции над предикатами.
Кванторные операции над предикатами»
по дисциплине «Дискретная математика»
Для студентов 3 курса
специальности «Компьютерные системы и комплексы»
Содержание:
Введение:......................................................................................................................................... 3
Предикаты........................................................................................................................................ 5
Понятие предиката....................................................................................................................... 5
Область определения и область значения предиката................................................................. 6
Логические операции над предикатами.......................................................................................... 8
Кванторные операции над предикатами....................................................................................... 11
Квантор общности ∀.......................................................................................................................................................... 11
Квантор существования ∃............................................................................................................................................... 13
Применение кванторов к естественному языку:........................................................................ 15
|
|
Операции над кванторами.......................................................................................................... 15
Контрольные вопросы:............................................................................................................... 16
Приложение 1............................................................................................................................. 17
Литература:.................................................................................................................................... 20
Введение
Логика есть наука о законах и формах познающего мышления. Логика изучает мышление, но не всякое мышление, а лишь те мыслительные процессы, которые направлены на обнаружение и обоснование истины, на решение некоторой задачи, на поиск путей преодоления тех или иных трудностей, встающих перед нами как в профессиональной деятельности, так и в обыденной жизни. Логику интересует лишь форма наших мыслей, но не их содержание. Разнообразие содержание укладывается в сравнительно небольшое число форм. Грубо говоря, логику интересуют сосуды - бутылки, ведра, бочки, - а не то, что в них налито.
У имени существительного "предикат" есть несколько значений.
1. Первое и основное относится к логике. Под предикатом подразумевают всё, сказанное об объекте. Объект может "гулять", "быть красным", "не гулять" - все эти характеристики объекта и являются предикатами.
2. В программировании предикат - это определённая функция, с помощью которой некие элементы являются либо "истинными", либо "ложными". Зачем программисту предикаты? Все знают, что в программах бывают ошибки (bugs). Существуют специальные теории, посвященные тому, как лучше их находить и исправлять (debugging дословно означает "выведение клопов"). Зачастую нахождение ошибки — очень нетривиальная задача, так как ее последствия могут сказываться совершенно в другом месте программы и быть весьма неожиданными. При этом часто забывается тот очевидный факт, что ошибку гораздо легче предотвратить при написании программы, нежели найти и исправить потом. Существуют методы проектирования программ (по крайней мере, небольших), позволяющие не только написать правильную программу, но и получить одновременно с этим совершенно строгое доказательство ее правильности. Однако для того,
|
|
чтобы изучить какую-либо теорию, необходимо выучить язык, на котором теория может быть изложена. Язык предикатов — это именно тот язык, на котором можно строго сформулировать постановку задачи и доказать правильность конкретной программы.
3. В лингвистике предикат (предикатив) - это особый вид сказуемого (если говорить о современном русском языке). Эти сказуемые выражают, скорее, не действия, а состояния: "Ты мне не рад?". Видите, подлежащее "ты", в общем-то, ничего не делает. Просто он(о), возможно, не рад. Для особо старательных студентов я рекомендую прочитать статьи по этому разделу. Узнаете очень много нового!
Предикаты
Понятие предиката.
В математике часто рассматриваются предложения, зависящие от одной или нескольких переменных. Например, предложение А: «|x|=x» - не является высказыванием, так как о его истинности ничего нельзя сказать без знания конкретного значения x; для x≥0 это выражение истинно, для x<0 ложно.
Определение 1: Предложение, содержащее переменные, которые при замене их на возможные значения становятся высказываниями, называются предикатом или высказывательной формой.
Определение 2: Предикат - логическая функция от некоторого числа предметных элементов, которая определяет свойства объекта или отношения между объектами.
Определение: Предикат, зависящий от одной переменной, называют одноместным. Предикат, зависящий от n переменных, называют n- местным предикатом.
Таким образом, бывают двухместные, трехместные и т.д. предикаты.
Любое высказывание является нуль-местным предикатом.
Пример 1.
Предложение А(x): «|x|=x» является предикатом одной переменной (одноместным).
Пример 2.
Предложение "Река х впадает в озеро Байкал" является одноместным предикатом, определенным над множеством всех названий рек. Подставив вместо предметной переменной х название "Баргузин", получим высказывание "Река Баргузин впадает в озеро Байкал". Это высказывание истинно. Подставив вместо предметной переменной х название "Днепр", получим ложное высказывание "Река Днепр впадает в озеро Байкал".
Пример 3.
Предложение (выражение) «х2+y2≤9» является двухместным предикатом, заданным над множествами R, R. Множества, на которых задан двухместный предикат, совпадают (говорят, что это "двухместный предикат задан на множестве R2"). Пара действительных чисел 2, 2 превращает данный предикат в истинное высказывание: «22+22≤9», а пара чисел 2, 3 — в ложное:
«22+32≤9».
Определение: Предикат, заданный на множестве А1, А2, …,Аn, называется:
1. Тождественно истинным, если при любой подстановке вместо переменных х1, х2, …, хn любых конкретных предметов а1, а2, …, аn из множеств А1, А2, …,Аn он превращается в истинное высказывание;
2. Тождественно ложным, если при любой подстановке вместо переменных х1, х2, …, хn любых конкретных предметов а 1, а2, …, аn из множеств А1, А2, …, Аn он превращается в ложное высказывание;
3. Выполнимым (опровержимым), если существует по крайней мере один набор предметов а1, а2, …, аn из множеств А1, А2, …, Аn, при подстановке которого вместо соответствующих предметных переменных в предикат последний превращается в истинное (ложное) высказывание.
|
|
Пример 4.
Предикат «х2-1=(х-1)(х+1)» является одноместным тождественно истинным на множестве действительных х, а предикат «х4+1<0» одноместным тождественно ложным при всех действительных х.
Пример 5.
Одноместный предикат "Город х расположен на берегу реки Волги", определенный на множестве названий городов. Существуют города, названия которых превращают данный предикат в истинное высказывание, или, иначе, удовлетворяют этому предикату (например, Ульяновск, Саратов и т. д.). Но существуют города, названия которых превращают его в ложное высказывание, или, иначе, не удовлетворяют этому предикату (например, Прага, Якутск и т.д.). Данный предикат является выполнимым.
Пример 6.
Одноместный предикат "sin2x+cos2x=1", определенный на множестве действительных чисел, тождественно истинный.
Домашнее задание: Самостоятельно докажите, почему предикат в примере 6 тождественно истинный?
Пример 7.
Двухместный предикат "х2+y2<0", заданный на множестве действительных чисел, является тождественно ложным предикатом, потому что любая пара действительных чисел превращает его в ложное высказывание (не удовлетворяет ему).
Область определения и область значения предиката.
Определение: Совокупность всех допустимых значений переменной x
называется областью определения предиката. Обозначается u A
Определение: Совокупность значений x, обеспечивающих истинность предиката, называется множеством истинности предиката. Обозначается IA.
Пример 8.
Предикат С(х): «Движение разрешено, если горит х цвет светофора» - одноместный предикат, выполнимый. Множество допустимых значений u A =«красный, желтый, зеленый», а множество истинности I A =«зеленый»
Пример 9.
Множеством истинности двухместного предиката "Точка x принадлежит прямой y ", заданного на множестве E всех точек плоскости и на множестве F всех прямых этой плоскости, является бинарное отношение принадлежности (инцидентности) между точками и прямыми плоскости.
|
|
Пример 10.
Множество истинности двухместного предиката S(x,y): «x2+y2=9», заданного на множестве R2, есть множество всех таких пар действительных чисел, которые являются координатами точек плоскости, образующими окружность с центром в начале координат и радиусом 3.
Пример 11.
Дан одноместный предикат " | a | >2". Область допустимых значений данного предиката R, а множество истинности (-∞; -2)∪(2; ∞) (или R\[-2; 2]).
Определение: Предикаты А(х) и В(х) с одной и той же областью определения называются равносильными, если они имеют одинаковые множества истинности. Их обозначают: А(х) ⟺ В(х)
Пример 12.
Предикаты А(х): «| x-1 | =x-1» и В(х): «х-1=√(х − 1)2» заданные на множестве действительных х, имеют одинаковые множества истинности х≥1, поэтому А(х) ⟺ В(х).
Пусть А(х) и В(х) – предикаты с некоторой частью области определения переменной х.
Определение: Предикат В(х) называют следствием предиката А(х), если множество истинности предиката А(х) является частью множества истинности предиката В(х).
Например, из равенства х =0 следует, что sin x =0, но не наоборот. Пояснение: Здесь даны два предиката: А(х): «х=0» и В(х): «sin x =0», определенные на множестве действительных чисел. Множеством истинности предиката А(х):
«х=0» является единственное значение х =0 среди всех действительных чисел, но множество истинности предиката В(х): «sin x =0», имеющего ту же область определения, содержит бесконечно много значений х, задаваемых формулой х =πk (k=0; ±1; ±2…), среди которых есть и х =0. Это означает, что предикат В(х) есть следствие предиката А(х).
Определение: Предикаты А(х) и В(х) одной и той же областью определения равносильны тогда и только тогда, когда В(х) есть следствие предиката А(х), и А(х) есть следствие предиката В(х).
Двухместный предикат – это более сложная структура, чем одноместный предикат. Двухместные предикаты также называют бинарными
отношениями. Например, неравенство «x · siny≥x2-y2» можно рассматривать как двухместный предикат А(х,y), принимающий значение «истинно» для тех пар значений х и y, для которых оно верно, и «ложно» при х и y, для которых оно неверно.
Над предикатами возможны те же логические операции, что и над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.