Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Кванторные операции над предикатами. Формулы логики предикатов
Задание 1 Доказать равносильности согласно варианту.
Пример выполнения задания 1 Пример. Доказать неравносильность: (" x) (P (x) Ú Q (x)) ® (" x) (P (x)) Ú (" x) (Q (x)). Решение: Определение 1. Две формулы, F и H логики предикатов называются равносильными на множестве M, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определенных на M, формулы превращаются в равносильные предикаты. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными. Равносильность формул будем обозначать так: F H. Определение 2. Формула логики предикатов называется общезначимой, или тавтологией (тождественно ложной или противоречием), если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на каких угодно множествах, она превращается в тождественно истинный (тождественно ложный) предикат. (Тот факт, что формула F является тавтологией, обозначается как и в алгебре высказываний ╞ F.) Покажем, что (" x) (P (x) Ú Q (x)) ® (" x) (P (x)) Ú (" x) (Q (x)). В самом деле, подставим вместо предикатных переменных P (x) и Q (x) конкретные предикаты A (x) и B (x), определенные на множестве N соответственно, где A (x) есть «х – четно», а B (x) есть «x – нечетно». Тогда левая формула превратится в высказывание (нульместный предикат) «каждое натуральное число нечетно, либо четно», которое истинно. Правая формула превращается в высказывание (нульместный предикат) «либо каждое натуральное число четно, либо каждое натуральное число нечетно», которое ложно. Нетрудно понять на основании определений 1 и 2, что формулы F и H равносильны тогда и только тогда, когда формула F → H является тавтологией: F @ H Û F ↔ H. Как и в алгебре высказываний, можно заменять одну равносильную формулу другой. Переход от одной равносильной формулы к другой называется равносильным преобразованием исходной формулы. В процессе равносильных преобразований формул логики предикатов могут использовать равносильности, известные из алгебры высказываний.
Задание 2 Является ли формула, заданная согласно варианту, общезначимой?
Пример выполнения задания 2 Пример. Выяснить, является ли формула логики предикатов ("y) ($x) (P(x,y) Ù P(y,y)) выполнимой или общезначимой на двухэлементном множестве {a,b}. Решение: Поскольку на двухэлементном множестве {a,b} высказывание ("x)(R(x)) эквивалентно конъюнкции R(a) Ú R(b), а высказывание ($x) (R(x)) – дизъюнкции R(a) Ú R(b), поэтому данная формула равносильна формуле ($x) (P(x,a) Ù P(a,a)) Ù ($x) (P(x,b) Ù P(b,b)), которая, в свою очередь, равносильна формуле [(P(a,a) Ù P(a,a)) Ú (P(b,a) Ù P(a,a))] Ù [(P(a,b) Ù P(b,b)) Ú (P(b,b) Ù P(b,b)))] Одна двухместная предикатная переменная P(x,y) исходной формулы как бы распалась на четыре пропозициональных переменных P(a,a), P(a,b), P(b,a), P(b,b) последней формулы, потому что при постановке в исходную формулу вместо P(x,y) двухместного предиката, определенного на {a,b}, указанные четыре переменные превратятся в (вообще говоря, различные) конкретные высказывания. Так что последняя формула есть по сути дела формула алгебры высказываний. Чтобы это увидеть совсем отчетливо, обозначим указанные четыре пропозициональные переменные буквами P, R, Q, S соответственно. Тогда полученная формула примет вид:
[(PÙP)Ú(QÙP)]Ù[(RÙS)Ú(SÙS)]. Составив таблицу истинности данной формулы алгебры высказываний (или каким-либо другим способом, как это делалось в алгебре высказываний), легко установить, что формула не является тавтологией, но выполнима: она превратится в истинное высказывание, если вместо P и S подставить истинные высказывания, а вместо Q и R – ложные. Применительно к исходной формуле логики предикатов это означает, что она не общезначима на двухэлементном множестве, но выполнима в нем: она превратится в выполнимый предикат, если вместо предикатной переменной P(x,y) подставить в формулу такой конкретный двухместный предикат, который при одинаковых значениях его предметных переменных x и y превращается в истинные высказывания, а при разных – в ложные.
Задание 3 Варианты 1-8: Считая одноместный предикат Р(х) заданным на множестве М, докажите утверждение согласно варианту. Варианты 9-15: Пусть P(x) и Q(x) – такие одноместные предикаты, заданные над одним и тем же множеством M, что высказывание 1 истинно/ложно согласно варианту, доказать истинность/ложность высказываний согласно варианту.
Примеры выполнения задания 3 Пример 1. Считая одноместный предикат Р(х) заданным на множестве М, докажите что λ[("x)(P(x))]=0 Û P+≠M. Решение: По определению квантора общности, высказывание ("x) (P(x)) ложно тогда и только тогда, когда предикат Р(х) опровержим, т.е. когда он не на всех элементах из M превращается в истинное высказывание. Это и означает, что не все элементы из М входят в множество истинности предиката Р(х), т.е. Р+ ≠ М. Пример 2. Пусть P(x) и Q(x) – такие одноместные предикаты, заданные над одним и тем же множеством M, что высказывание: ("x)[ P(x)→ (P(x) Ú (Q(x) → P(x)))] ложно. Докажите, что высказывание ("x) (P(x)) ложно, а высказывание ($x) (Q(x)) истинно. Решение: Из условия по определению квантора общности следует, что λ[P(a) → (P(a) Ú (Q(a) → P(a)))] = 0 для некоторого элемента a Î M. Отсюда по определению импликации, заключаем, что λ[P(a)] = 1 и λ[(P(a) Ú (Q(a) → P(a))] = 0. По определению отрицания из первого из двух последних равенств следует, что λ[P(a)] = 0, а из второго – λ[ Q(a) → P(a))] = 0, т.е. λ[Q(a) → P(a)] = 1. Поскольку, кроме того, λ[P(a)] = 0, то из последнего соотношения по определению импликации заключаем, что λ[Q(a)] = 0, т.е. λ[Q(a)] = 1. Итак, λ[P(a)] = 0 для некоторого a Î M. Следовательно, по определению квантора общности заключаем, что высказывание ("x) (P(x)) ложно. Так как λ[Q(a)] = 1, то отсюда по определению квантора существования следует, что высказывание ($x) (Q(x)) истинно.
Задание 4 Варианты 1-8: Какими могут быть множества Р+ и Q+ истинности предикатов Р(х) и Q(x) соответственно, заданных над непустым множеством М, если известно, что высказывание согласно варианту истинно? Варианты 9-15: Какими могут быть множества Р+ и Q+ истинности предикатов Р(х) и Q(x) соответственно, заданных над непустым множеством М, если известно, что высказывание согласно варианту ложно?
Примеры выполнения задания 4 Пример 1. Какими могут быть множества Р+ и Q+ истинности предикатов Р(х) и Q(x) соответственно, заданных над непустым множеством М, если известно, что следующее высказывание истинно: ("x) (P(x) Ú Q(x)) Ù ($x) (P(x) → (x)). Решение: По определению конъюнкции двух высказываний из условия следует, что λ[("x) (P(x) Ú Q(x))] = 1; (1) и λ[($x) (P(x) → Q(x))] = 1. (2) Далее, из (1) по определению отрицания заключаем, что λ[("x) (P(x) Ú Q(x))] = 0. (3) По определению квантора общности (3) означает, что предикат P(x) Ú Q(x) не является тождественно истинным, т.е. что его множество истинности не есть все множество М, т.е. (P(x) Ú Q(x))+ ≠ M, т. е. Из (2) по определению квантора существования следует, что предикат P(x)→ Q(x) выполним, т.е. его множество истинности не пусто: (P(x) → Q(x))+ ≠ Æ, т.е. (P(x)ÚQ(x))+ ≠ Æ, или Итак, окончательно мы получаем, что множества Р+ и Q+ должны удовлетворять следующим условиям: Q+ Ú P+, причем либо P+ ≠ M, либо Q+ ≠ Æ.
Пример 2. Какими могут быть множества Р+ и Q+ истинности предикатов Р(х) и Q(x) соответственно, заданных над непустым множеством М, если известно, что следующее высказывание ложно: ($x) (P(x) Ù Q(x)) → ("x) (P(x) → Q(x))? Решение: По определению импликации двух высказываний из условия задачи следует, что λ[($x) (P(x) Ù Q(x))] = 1; (1) и λ[("x) (P(x) → Q(x))] = 0. (2) Далее, из (1) заключаем, что (P(x) Ù Q(x))+ ≠ Æ, т.е. P+ ∩ Q+ ≠ Æ Из (2) по определению операции отрицания следует, что λ[("x) (P(x) → Q(x))] = 1, откуда следует, что (P(x) → Q(x))+ = M. Следовательно,
Это означает, что P+ Í Q+. Кроме того, P+ ∩ Q+ ¹ Æ. Итак, Æ ¹ P+ Í Q+.
Задание 5 Варианты 1-8: Покажите, что каждая интерпретация формул согласно варианту на одноэлементном множестве дает истинное высказывание. Варианты 9-15: Покажите, что при интерпретации формул согласно варианту на двухэлементном множестве не всегда получается истинное высказывание.
Примеры выполнения задания 5 Пример 1. Покажите, что каждая интерпретация следующей формулы на одноэлементном множестве дает истинное высказывание: P (y) → (" x) (P (x)). Решение: Как известно, предикат на множестве M есть некоторая функция, заданная на этом множестве и принимающая значения в двухэлементном множестве {0, 1}. Тогда, как легко понять, если М состоит из одного элемента а, т.е. М = { а }, то на нем можно задать лишь два конкретных предиката (функции) А 1(х) и А 2(х) следующим образом: A 1(a) =0, A 2(a)=1. При интерпретировании данной формулы нужно входящую в нее предикатную переменную Р назвать одним из конкретных предикатов А 1 или А 2, а свободную предметную переменную у – некоторым предметом из М (там их всего один – а). Сведем в таблицу всевозможные интерпретации данной формулы:
Пример 2. Покажите, что при интерпретации следующей формулы на двухэлементном множестве не всегда получается истинное высказывание: P (y) → (" x) (P (x)). Решение. На двухэлементном множестве М = { а, b } имеются уже четыре различных одноместных предиката. Они представляют собой функции А 1(х), А 2(х), А 3(х), А 4(х), заданные на двухэлементном множестве М = { а, b } и принимающие значения в двухэлементном множестве {0, 1} в соответствии со следующей таблицей:
Возможные интерпретации данной формулы в этом случае сведем в следующую таблицу:
Из таблицы видно, что предикат А 2(х) и предмет b Î М (характеризующийся тем, что А 2(b) = 1) превращают данную формулу в ложное высказывание А 2(b) → (" x) (А 2(x)). Руководствуясь этими соображениями, взяв, например, в качестве М множество {5, 6} (5, 6 – натуральные числа), а качестве предиката А 2(х) предикат «х ≤ 5». Тогда высказывание «5 ≤ 5» истинно, а высказывание «6 ≤ 5» - ложно (значит, в нашем случае а = 6, b = 5). Ложное высказывание, в которое превращается данная формула при этой интерпретации, выглядит так: 5 ≤ 5 → (" x) (x ≤ 5).
Задание 6 Докажите, что формула согласно варианту является тавтологией логики предикатов.
Примеры выполнения задания 6 Пример 1. Докажите, что следующая формула является тавтологией логики предикатов (" x) (P (x) → Q) ↔ ($ x) (P (x) → Q). Решение: Отметим, что предикатная переменная Q в этой формуле может быть не только 0-местной, но и любой n-местной, важно лишь, чтобы в нее не входила предметная переменная х. Итак, пусть Q есть Q (y 1,..., у n). Будем считать для краткости, что Q есть предикатная переменная Q (y). Предположим, что данная формула не является тавтологией. Тогда существуют такие конкретные предикаты А (х) и В (у), определенные на множествах М и М 1 соответственно, что предикат (от y): (" y) (A (x) → B(y)) ↔ ($ x) (A(x) → B (y)) опровержим, т.е. обращается в ложное высказывание при подстановке вместо предметной переменной у некоторого конкретного предмета b из M 1: λ[(" x)(A (x)→ B (b))↔(($ x)(A (x))→ B (b))]=0. Эквивалентность ложна, если ее члены принимают разные значения истинности, т.е. могут представиться две возможности. Первая: λ[(" x) (A (x) → B (b))] = 1, (1) λ[($ x) (A(x)) → B(b)] = 0. (2) И вторая: λ[(" x) (A (x) → B (b))] = 0 (3) ,λ[($ x) (A (x)) → B (b)] = 1. (4).
Рассмотрим первую возможность. Из (2) по определению импликации имеем: [($ x) (A (x))] = 1, (5) λ[ B (b)] = 0. (6) Далее, из (5) по определению квантора существования заключаем, что предикат А (х) для некоторого а из М выполним, т.е. λ[ A (a)] = 1 (7) Вернемся к соотношению (1). По определению квантора общности предикат A (x) → B (b) – тождественно истинен. В частности, если вместо предметной переменной х подставить а из М, то получим истинное высказывание λ[ A (a) → B (b)] = 1. Но, учитывая (6) и (7), получаем λ[ A (a) → B (b)] = λ[ A (a)] → λ[ B (b)] = 1 → 0 = 0 – противоречие. Рассмотрим вторую возможность, выраженную в соотношениях (3), (4). Из (3), на основании определения квантора общности, следует, что предикат A (x) → B (b) опровержим, т.е. λ[ A (a) → B (b)] = 0 для некоторого a Î M. Тогда по определению импликации: λ[ A (a)] = 1, λ[ B (b)] = 0. (8) Ввиду последнего соотношения из соотношения (4) заключаем, что λ[($ x) (A (x))] = 0. Последнее означает тождественную ложность предиката А (х). В частности, для предмета a Î M имеем λ[ A (a)] = 0, что противоречит первому из соотношений (8). Итак, в каждом случае приходим к противоречию, доказывающему невозможность сделанного предположения. Следовательно, данная формула – тавтология. Пример 2. Докажите, что следующая формула является тавтологией логики предикатов: (" x) (P (x)) → (" x) (P (x) Ú Q (x)). Решение: Предположим, что формула не является тавтологией. Тогда существуют такие предикаты A (x) и В (х), определенные на множестве М, что высказывание (" x) (А (x)) → (" x) (А (x) Ú В (x)) ложно. Импликация ложна, если и только если: λ[(" x) (A (x))] = 1, (1) λ[(" x) (A (x)) Ú B (х)] = 0. (2) Из (2) по определению квантора общности следует, что предикат A (x)) Ú B (х) опровержим, т.е. найдется такой предмет a Î M, для которого λ[ A (a) Ú B (a)] = 0, т.е. λ[ A (a)] = 0 и λ[ В (a)] = 0. Но утверждение λ[ A (a)] = 0 противоречит общности (1), так как из него по определению квантора общности вытекает, что предикат А (х) тождественно истинный, т.е. ни при каком a Î M не превращается в ложное высказывание.
Задание 7 Применяя равносильные преобразования, приведите формулу согласно варианту к предваренной (пренексной) нормальной форме, т.е. к форме вида (Q 1 x 1) … (Q m xm) (F (x 1, …, xn)), где m < n, каждый Qi есть один из кванторов " или $ и формула F (x 1, …, xn) не содержит кванторов.
Примеры выполнения задания 7 Пример 1. Применяя равносильные преобразования, приведите следующую формулу согласно варианту к предваренной (пренексной) нормальной форме: ($ y) ((P (x) → Q (y)) → (" y) ((P (y) Ú (" z) (Q (z))) Решение: Данная формула представляет собой импликацию двух подформул, в каждой из которых имеется квантор по переменной у, так что и в первой подформуле, и во второй подформуле переменная у оказывается связанной. Это означает, что переменная у в первой подформуле и переменная у во второй подформуле никак не связаны между собой. Кроме того, в силу их связанности кванторами каждая из них может быть обозначена любой другой буквой. Это обозначение не имеет значения для данной формулы, но имеет исключительно важное значение для ее равносильного преобразования, начинающегося с процесса вынесения кванторов ($ y) и (" y) за знак импликации. Итак, начнем с того, что переменную y во второй подформуле данной формулы обозначим буквой t:
Теперь мы видим, что квантор существования по переменной у применяется к посылке импликации, в то время как следствие импликации не имеет свободной переменной у. Получаем:
Остается квантор общности по переменной z. Сначала выносим его за знак дизъюнкции (второй член дизъюнкции Р (t) не зависит от z свободно):
Наконец, как и в случае с квантором ("t), вынесем квантор (" z) за знак импликации
Задание 8 Выясните, будет ли выполняться в логике предикатов логическое следование согласно варианту.
Примеры выполнения задания 8 Пример 1. Выясните, будет ли выполняться в логике предикатов следующее логическое следование: (" x) (S (x) → P (x)) ╞ ($ x) (P (x) Ù S (x))? Решение: Предположим, что найдутся такие конкретные предикаты А (х) и В (х), заданные над конкретным множеством М, что λ[(" x) (B (x) → A (x))] = 1, (1) а λ[($ x) (A (x) Ù B (x))] = 0. (2) Из (1) по определению квантора общности следует, что λ[ B (a) → A (a))] = 1 (3) для любого предмета a Î M. Из (2) по определению квантора существования следует, что λ[ A (b) Ù B (b))] = 0 (4) для некоторого предмета b Î M. Отсюда видно, что если предикаты А (х) и В (х) взять такими, что
где λ[ A (b)] = 0 и λ[ A (x)] произвольно, если x ≠ b, то противоречия не получится, соотношения (3) и (4) будут выполняться, вместе с ними будут выполняться соотношения (1) и (2), которые и будут говорить о том, что рассматриваемое следование неверно. ТЕМА 7
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Последнее изменение этой страницы: 2021-11-27; просмотров: 416; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.133.161.153 (0.108 с.) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
. Последнее условие, как нетрудно понять, равносильно следующему: Q+ Ú P+.
. Отсюда следует, что 
(т.е. P+ ≠ M) или Q+ ≠ Æ.
Пересечем обе части этого равенства с P+:
,
