Высказывания и предикаты реферат

Обновлено: 02.07.2024

Аннотация: Рассматриваются основные понятия и сведения алгебры высказываний и предикатов – высказывания, предикаты, аксиомы, логические выражения и функции, эквивалентные выражения и приведение к эквивалентному выражению, другие сопутствующие понятия и факты логики, а также инфологические задачи.

Информатика , как было рассмотрено выше, изучает знаковые (алфавитные) системы. Алгебра – наиболее адекватный математический аппарат описания действий в них, поэтому алгебраический аппарат наилучшим образом подходит для описания информационных систем общей природы, отвлеченно от их предметной направленности. Информационные процессы хорошо формализуются с помощью различных алгебраических структур.

Алгеброй A называется некоторая совокупность определенных элементов X , с заданными над ними определенными операциями f (часто определяемые по сходству с операциями сложения и умножения чисел), которые удовлетворяют определенным свойствам – аксиомам алгебры.

Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции ).

Совокупность операций алгебры A называется ее сигнатурой, а совокупность элементов алгебры – носителем алгебры .

Утверждение ( высказывательная форма ) – основная единица , неделимая с точки зрения отражения смысла информации (семантики).

Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать ("сразу посмотрев на него"), истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь" , " true " и "fаlse" или "1" и "0".

Переменная , значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной.

Пример. Рассмотрим словосочетания:

Москва – столица США.
Житель города Москва.
5 – 7 + 8 .
5 – 9 + 28 = 4 .
В пятую неделю зимы было очень холодно.
В Антарктиде живут тигры.

Высказывание должно быть однозначно истинным или однозначно ложным, поэтому высказываниями являются только утверждения 1), 4), 6).

Пример. Не является высказыванием и "парадокс лжеца" (Эвбулид, учитель Демосфена, около 350 лет до н.э.): "То, что я сейчас утверждаю, – ложно", ибо если оно истинно – то оно ложно, а если допустить, что оно ложно, то оно истинно. Это неопределенная высказывательная форма . Аналогичный пример принадлежит известному математику, логику Гёделю (1931 г.): "То, что утверждается в этом предложении, не может быть доказано". Если его можно опровергнуть, то его нельзя доказать, а если его нельзя опровергнуть, то его можно доказать. Предложения такого рода не могут быть доказаны или опровергнуты в пределах того языка (той теории, алгебры ), с помощью которой они сформулированы. Известны многие подобные парадоксы.

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

Пример. Построим из ниже заданных простых высказываний составные, сложные высказывания , принимающие значение "истина" , "ложь" :

"Зима – холодное время года".
"Пальто – теплая одежда".
"Камин – источник тепла".

Истинным будет, например, сложное высказывание : "Зима – холодное время года и зимой носят пальто", а ложным будет, например, высказывание : "Некоторые ходят в пальто, поэтому на улице зима". Придумайте другие примеры.

Предикат – высказывательная форма с логическими переменными (множество значений этих переменных вполне определено), имеющая смысл при любых допустимых значениях этих переменных. Количество переменных в записи предиката называется его местностью.

Простые высказывания или предикаты не зависят от других высказываний или предикатов ("не разбиваемы на более простые"), а сложные – зависят хотя бы от двух простых.

Пример. Выражение "х = у" – предикат , "х > 5" – предикат , а "7 > 5" – высказывание . Утверждение "Хорошо" не является высказыванием , утверждение "Оценка студента А по информатике – хорошая" – простое высказывание , утверждение "Вчера была ясная погода, я был вчера на рыбалке" – сложное высказывание , состоящее из двух простых.

Логической (булевой) функцией f(х) называется некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = .

Пример. Заданы предикаты вида р = "число х делится нацело на 3" и q = "у – день недели" . Найдем множество истинности предикатов р и q , если " />
, " />
. Получаем, что " />
, " />
.

Множество логических переменных с определенными над ним операциями: " />
– отрицания или инверсии, – логического сложения или дизъюнкции, – логического умножения или конъюнкции называется алгеброй предикатов (и высказываний ) , если эти операции удовлетворяют следующим аксиомам :

Аксиома двойного отрицания:

$\overline<\overline<x> >=x$

Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции ):

$x \land y = y\land x, x \lor y = y \lor x$

Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов):

$(x \land y) \land z = x \land (y \land z), (x \lor y) \lor z = x \lor (y \lor z)$

Аксиомы одинаковых операндов:

$x\land x = x, x \lor x = x$

Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения):

$x \land (x \lor y) = x, x \lor (x \land y) = x$

Аксиомы распределения операции ( дизъюнкции относительно конъюнкции и наоборот):

$x \land (y \lor z) = (x \land y) \lor (x \land z), x \lor (y \land z) = (x \lor y) \land (x \lor z)$

Аксиомы де Моргана (перенесения бинарной операции на операнды):

$\overline<x\land y> = \overline\lor\overline, \overline<x\lor y>=\overline\land\overline$

Аксиомы нейтральности (взаимноинверсных множителей или слагаемых):

$x\land(y\lor\overline )=x, x\lor(y\land\overline)=x$

Аксиома существования единицы ( истина , true, 1) и нуля ( ложь , false, 0), причем,

$\overline<0> =1, \overline=0, \overline\lor x=1, \overline\land x = 0$

Из этих аксиом следует ряд полезных соотношений, например,

$x\land1=x,\\x\lor0=x,\\x\lor1=1,\\x\land0=0,\\ \overline \lor x=1,\\ \overline\land x=0$

Высказывание – это повествовательное предложение, про которое можно однозначно сказать, истинно оно или ложно.

Например:
A: натуральное число a делится на 2;
B: натуральное число a чётное.
Заметим, немного забегая наперёд, что в данном случае из А следует В, и из В следует А. Говорят, что эти высказывания эквивалентны: A ⇔ B.

п.2. Предикаты

Предикат – это предложение с переменной P(x), которое становится высказыванием при подстановке определённого значения переменной.
Предикат P(x) является функцией, которая определена на некотором множестве значений x>, и ставит ему в соответствие два значения – истина или ложь.

Например:
P(x): x – объект с четырьмя ногами
При x = слон – предикат становится истинным высказыванием, P("слон" )=1
При x = муравей – предикат становится ложным высказыванием, т.к. у муравья 6 ног, P(муравей)=0
При x = стол – предикат становится истинным высказыванием, P("стол" )=1
При x = человек – предикат становится ложным высказыванием, т.к. у человека 2 ноги, P(человек)=0

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

Например:
P(x):|x| ≥ 0 – выполняется при любом значении x, это тождественный предикат.
$\mathrm>$

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

Например:
P(x, y): x делится на y – двуместный предикат, который становится истинным высказыванием на парах значений переменных (15;5), (14;7), (16;4) и т.д.
P(a, b):(a + b) 2 = a 2 + 2ab + b 2 – является тождественным двуместным предикатом, т.к. выполняется для любых a и b.

п.3. Кванторы

Единственности и существования

Пусть P(x) – одноместный предикат. Чтобы установить истинность высказывания (∃x)P(x), достаточно найти хотя бы один такой x*, что P(x* ) становится истинным высказыванием.

Существуют натуральные числа, которые делятся на 13

Например x = 26

Существуют треугольники, у которых все углы равны

Например, равносторонний треугольник со стороной 1

Пусть P(x) – одноместный предикат. Чтобы установить ложность высказывания (∀x)P(x), достаточно найти хотя бы один такой x*, что P(x* ) становится ложным высказыванием.

Любое натуральное число делится на 5

Например x = 6 на 5 не делится

У любого выпуклого четырехугольника диагонали перпендикулярны

Например, у прямоугольника со сторонами 3 и 4 угол между диагоналями ≈ 74° ≠ 90°

Пусть P(x) – одноместный предикат. Чтобы установить истинность высказывания (∀x)P(x), необходимо доказать, что предикат P(x) является тождеством.

Разность квадратов двух любых выражений равна произведению суммы и разности

Сумма углов любого треугольника равна 180°.

(∀ABC) ∠A + ∠B + ∠C = 180°

Третий класс задач (теорема) – самый сложный, т.к. требует не просто одного примера, а доказательства в общем случае.

п.4. Примеры

Пример 1. Запишите по два высказывания (A – истинное, B – ложное), относящиеся к
а) физике
A: Плотность равна отношению массы тела к его объему.
B: КПД механизма может быть больше 1.
б) химии
A: Гидроксид натрия – сильное основание.
B: Сульфат натрия – нерастворимая соль.
в) географии
A: На Земле шесть материков.
B: На Земле три океана.

Пример 2. Запишите по два предиката, относящиеся к
а) физике
A(h): Потенциальная энергия прямо пропорциональна высоте h.
B(v): Сила лобового сопротивления прямо пропорциональна квадрату скорости v 2 .
б) химии
A(x,y): Между основанием x и кислотой y проходит реакция нейтрализации.
B(x): Металл x вытесняет водород из HCl.
в) географии
A(x,y,z): День x является днём y солнцестояния в z полушарии.
B(x,y): Река x впадает в море y.

Пример 3. С каким из кванторов предикат x 2 + 4 = 12 станет истинным высказыванием?
Если запишем (∀x) x 2 + 4 = 12 – это ложное высказывание, т.к., например, при x=0 оно не выполняется.
Если запишем (∃x) x 2 + 4 = 12 – это истинное высказывание, т.к., например, при $\mathrm>$, оно выполняется.
Если запишем (∃x!) x 2 + 4 = 12 – это ложное высказывание, т.е. решений у данного уравнения не одно, а два: $\mathrm=2\sqrt>$
Ответ: квантор существования ∃.

Пример 4. Найдите область истинности предиката: $$ P(x):\ \left\< \begin < l >\mathrm & \\ \mathrm & \end\right. $$ Решаем систему: $$ \left\< \begin < l >\mathrm <(x-4)(x-7)\geq 0>& \\ \mathrm <(x-2)(x-9)\lt 0>& \end\right. $$
Область истинности предиката: x ∈ (2;4] ∪ [7;9)
P(x) = 1 приx ∈ (2;4] ∪ [7;9)

ГОСТ

Понятие предиката

Предикат - утверждение, которое содержит переменные, принимающие значение $1$ или $0$ (истинно или ложно) в зависимости от значений переменных.

Например, выражение $x=x^5$ является предикатом, т.к. оно является истинным при $x=0$ или $x=1$ и ложным при всех остальных значениях $x$.

Множество, на котором предикат принимает только истинные значения, называется множеством истинности предиката $I_p$.

Предикатом в программировании является функция, которая принимает один или более аргументов и возвращает значения булева типа.

Предикат называется тождественно-истинным, если на любом наборе аргументов он принимает истинное значение:

$P (x_1, \dots, x_n)=1$

Предикат называется тождественно-ложным, если на любом наборе аргументов он принимает ложное значение:

$P (x_1, \dots, x_0)=0$

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

Т.к. предикаты могут принимать только два значения (истинно/ложно или $0/1$), то к ним можно применять все операции алгебры логики: отрицание, конъюнкция, дизъюнкция и т.д.

Примеры предикатов

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

Готовые работы на аналогичную тему

Операции над предикатами

Рассмотрим применение операций алгебры логики к предикатам.

Логические операции:

Дизъюнкция двух предикатов $A(x)$ и $B(x)$ -- предикат , который принимает ложное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает ложное значение и принимает истинное значение во всех остальных случаях. Множество истинности предиката -- объединение областей истинности предикатов $A(x)$ и $B(x)$.

Отрицание предиката $A(x)$ -- предикат, который принимает истинное значение при всех значениях $x$ из $T$, при которых предикат $A(x)$ принимает ложное значение и наоборот. Множество истинности предиката $A(x)$ -- дополнение $T'$ к множеству $T$ в множестве $x$.

Множество истинности предиката -- объединение множества истинности предиката $B(x)$ и дополнения к множеству истинности предиката $A(x)$.

Над предикатами помимо логических операций можно выполнять квантовые операции: применение квантора всеобщности, квантора существования и т.д.

Кванторы

Кванторы -- логические операторы, применение которых к предикатам превращает их в ложные или истинные высказывания.

Квантор -- логические операции, которые ограничивают область истинности предиката и создают высказывание.

Чаще всего используют кванторы:

В математической логике существует понятие связывание или квантификация, которые обозначают приписывание квантора к формуле.

Примеры применения кванторов

С помощью квантора всеобщности можно записать следующие ложные высказывания:

любое натуральное число делится на $7$;

каждое натуральное число делится на $7$;

все натуральные числа делятся на $7$;

который будет иметь вид:

Для записи истинных высказываний используем квантор существования:

существуют натуральные числа, которые делятся на $7$;

найдётся натуральное число, которое делится на $7$;

хотя бы одно натуральное число делится на $7$.

Запись будет иметь вид:

Таким образом, предикат можно превратить в высказывание, если поставить перед предикатом квантор.

Операции над кванторами

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

Рассмотрим предложения и выделим среди них предикаты, указав область истинности каждого из них:

Вы можете изучить и скачать доклад-презентацию на тему Предикаты. Презентация на заданную тему содержит 18 слайдов. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций в закладки!

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

Одноместный предикат P(x) -произвольная функция переменного х, определенного на множестве М и принимающая значения из множества <1,0>. Одноместный предикат P(x) -произвольная функция переменного х, определенного на множестве М и принимающая значения из множества <1,0>. Двухместный предикат Р(х;у) - функция двух переменных х и у, определенная на множестве М=М1хМ2 и принимающая значения из множества <1,0>.

Тождественно-истинным называется предикат, истинный всюду на области определения Т(Р)=D(Р). Тождественно-истинным называется предикат, истинный всюду на области определения Т(Р)=D(Р). Тождественно-ложным называется предикат, множество истинности которого пусто Т(Р)=Ø.

Присоединение квантора с переменной к предикатной формуле называется навешивание квантора на переменную х. Переменная при этом называется связной и вместо нее подставлять константы уже нельзя. Присоединение квантора с переменной к предикатной формуле называется навешивание квантора на переменную х. Переменная при этом называется связной и вместо нее подставлять константы уже нельзя. Если квантор навешивается на формулу с несколькими переменными, то он уменьшает число несвязных переменных в этой формуле.

Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), В высказывании же х называют связанной квантором всеобщности. Переменная, на которую навешивается квантор называется связанной. Выражение, на которое навешиваете квантор, называется областью действия квантора. Кванторы общности и существования называют двойственными относительно друг друга.

Равносильные формулы логики предикатов Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенные к области М.

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

Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную) нормальную форму ПНФ. Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную) нормальную форму ПНФ. В ней кванторные операции, либо полностью отсутствуют , либо они используются после всех операций алгебры.

Читайте также: