Предикаты и кванторы конспект урока 10 класс информатика

Обновлено: 05.07.2024

Предикат - утверждение, которое содержит переменные, принимающие значение $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$.

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

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

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

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

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

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

Определение. Предложения, содержащие переменные, истинность или ложность которого зависит от значения переменного, входящего в него, называется предикатом. Другими словами, это функция, заданная на определенном множестве. Обозначение Р(х), Р(х,у), …, Р(х1,х2, …,хn).

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

Считается, что с каждым предикатом задано множество, из которого выбирают значение переменных. Такое множество называют областью определения предиката. Обозначение D(P).

Пример. Р(х)=«х+3 . Какое бы число не поставить вместо х, будем получать либо ложное либо истинное высказывание.

Подмножеством области определения предиката, на котором он принимает значение истинность, называется множеством истинности данного предиката. Обозначение М(Р). М(Р) D(P).

Пример для Р(х)=«х+3

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

Отрицанием предиката Р(х) называется новый предикат , определённый на множестве D(Р) и истинный при тех значениях переменных х, при которых предикат Р(х) ложен.

Пример. =\ =то есть убрать из D(P) все числа, делящиеся на 9.

Конъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х)⋀Q(x), определённый на множестве D(Р) и истинный при тех значениях переменных х, при которых истины одновременно оба предиката P(x) и Q(x).

Пример. = =

Дизъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х)VQ(x), определённый на множестве D(Р) и истинный при тех значениях переменных х, при которых истинен хотя бы один из предикатов P(x) и Q(x).

= =

Импликацией двух предикатов Р(х) и Q(x) называется новый предикат Р(х) Q(x), определённый на множестве D(Р) и ложный при тех значениях переменных х, при которых предикат P(x) истинен, а предикат Q(x) ложен.

Пример. =\ =

Эквиваленцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х) ↔ Q(x), определённый на множестве D(Р) и истинный при тех значениях переменных х, при которых либо оба предиката истины, либо оба предиката ложны.

= ,

Кванторы. Операции навешивания квантора

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

Задания для самостоятельной работы

Объяснить, почему следующие выражения имеют значение истина или ложь, описать выражения словами

Для следующих предложений выделить предикаты и для каждого из них указать область истинности:

однозначное число х кратно 3;

На множестве M = определены предикаты: P(x) - "число Х делится на 6" и Q(x) - "число Х 30". Найдите область истинности предикатов , , , ,

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

а) Некоторые машины умнее людей.

б) Любой играет в теннис лучше Фрэда.

в) Для каждого действует существует равное и противоположно направленное противодействие.

г) Каждый игрок в гольф, в конце концов, будет обыгран более сильным игроком

1. Предикаты и кванторы. Действия над предикатами и их свойства Ирина Борисовна Просвирнина

• Предикаты
• Кванторы
• Ограничительные кванторы
• Логические эквивалентности выражений,
содержащих кванторы
• Отрицания выражений, содержащих кванторы
• Вложенные кванторы

2. Предикаты

Предложения, содержащие переменные, часто
встречаются в
математических утверждениях;
компьютерных программах;
спецификациях систем.

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Методическая разработка урока по информатике с применением электронного обучения и дистанционных технологий

1. Внимательно изучите предложенный материал по теме.

Логическое высказывание

Давайте для начала пройдемся по терминологии.

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

Логическое высказывание – это некое рассуждение, которое можно отнести к истинным или ложным высказываниям.

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

При этом логическое высказывание может принимать только два значения: правда или ложь.

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

Если некоторая операция приводится к одному результату, то она называется унарной. Если же операция имеет два решения, то она бинарная.

Инверсия – это операция, которая приводит к тому, что получается новая операция в результате отрицания первоначальной.

Геометрический смысл инверсии:

То есть если некая операция приводит к отрицанию, то она находится за пределами правды.

Если некая операция соединяет несколько высказываний, то её называют конъюнкция. То есть одновременно используют два или более события.

Таблица истинности операции конъюнкции:

Дизъюнкция – это операция, обратная конъюнкции. То есть существуют все случаи, кроме тех, когда несколько множеств пересекается.

Таблица истинности операции дизъюнкции:

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

Таблица истинности операции строгой дизъюнкции:

Данная операция предлагает некое следствие после определенной операции.

Таблица истинности операции импликации:

Эквивалентность – это такая операция, при которой любые несколько событий считаются равноправными.

Таблица истинности операции эквивалентности:

Связь между логическими операциями:

Квантор – это логические операции, которые имеют некоторые ограничения.

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

2. Составьте опорный конспект по плану:

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

2) Логические высказывания

3. Выполните тест по теме, выбрав любой вариант из предложенных.

1. Как называется логическое умножение?

а) инверсия б) дизъюнкция с) конъюнкция д) импликация

2. Какое из обозначений не применяется для инверсии

а) НЕ б) │ с) ¬ д) NOT

3. У какой из логических функций следующая таблица истинности:

4. Переведите из десятичной системы счисления число 827₁₀ в двоичную и выберите ответ:

а) 100000011 б) 11111110 с) 1100111011 д) 1010111

а) А и (В и С) б) А и В с) (А и В) или С д) А

6. Определите, какое из высказываний истинное, если

а) истинно только А б) истинно только Б

с) истинны А и Б д) оба высказывания ложны

8. Переведите из двоичной системы счисления число 111011101₂ в десятичную и выберите ответ:

а) 477 б) 1024 с) 716 д) 2596

9. Переведите из десятичной системы счисления число 33₁₀ в двоичную и выберите ответ :

а) 10001 б) 11010 с) 110100 д) 100001

10. Переведите из двоичной системы счисления число 111011₂ в десятичную и выберите ответ:

а) 28 б) 41 с) 59 д) 78

1. Как называется логическое сложение?

а) инверсия б) дизъюнкция с) конъюнкция д) импликация

2. Переведите из двоичной системы счисления число 11001110111₂ в десятичную и выберите ответ:

а) 1258 б) 512 с) 3010 д) 1655

3. У какой из логических функций следующая таблица истинности:

а) инверсия б) конъюнкция с) дизъюнкция

4. Какое из предложений не является высказываниями ?

а) Внимание! б) Число 6 – четное

с) Некоторые рыбы – хищники д) Эта ночь холодная .

а) А и (В и С) б) А и В с) (А и В) или С д) А

6. Определите, какое из высказываний истинное, если

а) истинно только А б) истинно только Б

с) истинны А и Б д) оба высказывания ложны

а) 1 б) 2 с) 3 д) 4

8. Переведите из десятичной системы счисления число 726₁₀ в двоичную и выберите ответ :

а) 100000011 б) 1011010110 с) 1100111011 д) 1010111

9. Переведите из десятичной системы счисления число 26₁₀ в двоичную и выберите ответ :

а) 10001 б) 11010 с) 110 д) 1011

10. Переведите из двоичной системы счисления число 110011₂ в десятичную и выберите ответ:

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