Область определения и область значения предиката

Логические операции над предикатами.

Кванторные операции над предикатами»

по дисциплине «Дискретная математика»

Для студентов 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.

Предложение (выражение) «х²+y²≤9» является двухместным предикатом, заданным над множествами R, R. Множества, на которых задан двухместный предикат, совпадают (говорят, что это "двухместный предикат задан на множестве R2"). Пара действительных чисел 2, 2 превращает данный предикат в истинное высказывание: «2²+2²≤9», а пара чисел 2, 3 — в ложное:

«2²+3²≤9».

 

Определение: Предикат, заданный на множестве А₁, А₂, …,А_n, называется:

1. Тождественно истинным, если при любой подстановке вместо переменных х₁, х₂, …, х_n любых конкретных предметов а₁, а₂, …, а_n из множеств А₁, А₂, …,А_n он превращается в истинное высказывание;

2. Тождественно ложным, если при любой подстановке вместо переменных х₁, х₂, …, х_n любых конкретных предметов а ₁, а₂, …, а_n из множеств А₁, А₂, …, А_n он превращается в ложное высказывание;

3. Выполнимым (опровержимым), если существует по крайней мере один набор предметов а₁, а₂, …, а_n из множеств А₁, А₂, …, А_n, при подстановке которого вместо соответствующих предметных переменных в предикат последний превращается в истинное (ложное) высказывание.

 

Пример 4.

Предикат «х²-1=(х-1)(х+1)» является одноместным тождественно истинным на множестве действительных х, а предикат «х⁴+1<0» одноместным тождественно ложным при всех действительных х.

Пример 5.

Одноместный предикат "Город х расположен на берегу реки Волги", определенный на множестве названий городов. Существуют города, названия которых превращают данный предикат в истинное высказывание, или, иначе, удовлетворяют этому предикату (например, Ульяновск, Саратов и т. д.). Но существуют города, названия которых превращают его в ложное высказывание, или, иначе, не удовлетворяют этому предикату (например, Прага, Якутск и т.д.). Данный предикат является выполнимым.

 

Пример 6.

Одноместный предикат "sin²x+cos²x=1", определенный на множестве действительных чисел, тождественно истинный.

 

Домашнее задание: Самостоятельно докажите, почему предикат в примере 6 тождественно истинный?

Пример 7.

Двухместный предикат "х²+y²<0", заданный на множестве действительных чисел, является тождественно ложным предикатом, потому что любая пара действительных чисел превращает его в ложное высказывание (не удовлетворяет ему).

 

Область определения и область значения предиката.

Определение: Совокупность всех допустимых значений переменной x

называется областью определения предиката. Обозначается u A

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

 

Пример 8.

Предикат С(х): «Движение разрешено, если горит х цвет светофора» - одноместный предикат, выполнимый. Множество допустимых значений u A =«красный, желтый, зеленый», а множество истинности I _A =«зеленый»

Пример 9.

Множеством истинности двухместного предиката "Точка x принадлежит прямой y ", заданного на множестве E всех точек плоскости и на множестве F всех прямых этой плоскости, является бинарное отношение принадлежности (инцидентности) между точками и прямыми плоскости.

 

Пример 10.

Множество истинности двухместного предиката S(x,y): «x²+y²=9», заданного на множестве R2, есть множество всех таких пар действительных чисел, которые являются координатами точек плоскости, образующими окружность с центром в начале координат и радиусом 3.

 

Пример 11.

Дан одноместный предикат " | a | >2". Область допустимых значений данного предиката R, а множество истинности (-∞; -2)∪(2; ∞) (или R\[-2; 2]).

 

Определение: Предикаты А(х) и В(х) с одной и той же областью определения называются равносильными, если они имеют одинаковые множества истинности. Их обозначают: А(х) ⟺ В(х)

 

Пример 12.

Предикаты А(х): «| x-1 | =x-1» и В(х): «х-1=√(х − 1)²» заданные на множестве действительных х, имеют одинаковые множества истинности х≥1, поэтому А(х) ⟺ В(х).

 

Пусть А(х) и В(х) – предикаты с некоторой частью области определения переменной х.

Определение: Предикат В(х) называют следствием предиката А(х), если множество истинности предиката А(х) является частью множества истинности предиката В(х).

 

Например, из равенства х =0 следует, что sin x =0, но не наоборот. Пояснение: Здесь даны два предиката: А(х): «х=0» и В(х): «sin x =0», определенные на множестве действительных чисел. Множеством истинности предиката А(х):

«х=0» является единственное значение х =0 среди всех действительных чисел, но множество истинности предиката В(х): «sin x =0», имеющего ту же область определения, содержит бесконечно много значений х, задаваемых формулой х =πk (k=0; ±1; ±2…), среди которых есть и х =0. Это означает, что предикат В(х) есть следствие предиката А(х).

 

Определение: Предикаты А(х) и В(х) одной и той же областью определения равносильны тогда и только тогда, когда В(х) есть следствие предиката А(х), и А(х) есть следствие предиката В(х).

 

Двухместный предикат – это более сложная структура, чем одноместный предикат. Двухместные предикаты также называют бинарными

отношениями. Например, неравенство «x · siny≥x²-y²» можно рассматривать как двухместный предикат А(х,y), принимающий значение «истинно» для тех пар значений х и y, для которых оно верно, и «ложно» при х и y, для которых оно неверно.

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