Заказ №223094 Математическая логика готовое

Для приведенных формул логики высказываний построить соответствующие им логические функции в виде таблиц истинности, определить общезначимость, выполнимость (невыполнимость) и число моделей формулы. Решение а) Таблица истинности: p Пояснение к таблице: если в конъюнкции есть хотя бы одна ложь, то вся конъюнкция ложна.

Поэтому некоторые ячейки не заполнены: они уже не влияют на значение функции. Формула выполнимая (не общезначимая и не тождественно ложная), потому что существуют наборы значений переменных p,q, на которых формула принимает значение 1, и есть наборы, на которых формула принимает значение 0. Число моделей формулы равно числу наборов, на которых формула принимает значение 1: в данном случае таких наборов 2. б)

Таблица истинности: p Формула выполнимая (не общезначимая и не тождественно ложная). Число моделей равно 13. в) Таблица истинности: 1 1 1 0 0 1 Формула выполнимая (не общезначимая и не тождественно ложная). Число моделей равно 3. г) Таблица истинности: Формула выполнимая (не общезначимая и не тождественно ложная). Число моделей равно 13. д) Таблица истинности: p Формула выполнимая (не общезначимая и не тождественно ложная). Число моделей равно 3. 2.

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

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

в) Либо рост инфляции эквивалентен снижению уровня жизни, либо рост производства влечет то, что уровень жизни не снижается. г) Если будет идти дождь или снег, то футбольный матч либо не состоится, либо его результат не будет отображать соотношение сил. д) Если животное млекопитающее и имеет острые зубы и имеет клыки и не ест траву, то это хищник. Решение а) Обозначения для простых высказываний: Рабочие упорствуют =p; Администрация упорствует =q; Забастовка урегулирована =r;

Правительство добилось судебного запрещения =s; Войска посланы на завод =t. Формула сложного высказывания: (p∨. Таблица истинности: Формула выполнимая (не общезначимая и не тождественно ложная). Число моделей формулы равно 20. б) Обозначения для простых высказываний: Вечером будет туман =p; Вечером будет снег =q; Джон остается дома =r; Джон вынужден взять такси =s. Формула сложного высказывания: (p∨q)→(r∨s).

Возможно вам будут полезны данные страницы:

Линейно связные множества
Дифференциальные уравнения высших порядков
Новое время в Европе как особая фаза всемирно исторического процесса
Ускорение, вектор, производная скорости, теорема Пифагора для модуля полного ускорения

Таблица истинности: Формула выполнимая (не общезначимая и не тождественно ложная). Число моделей формулы равно 13. в) Обозначения для простых высказываний: Инфляция растет =p; Уровень жизни снижается =q; Производство растет =r; Формула сложного высказывания: (p↔q)⊕(r→¬q). Таблица истинности: p Формула выполнимая (не общезначимая и не тождественно ложная). Число моделей формулы равно 4. г) Обозначения для простых высказываний: Будет идти дождь =p; Будет идти снег =q; Футбольный матч состоится =r; Результат матча будет отображать соотношение сил =s. Формула сложного высказывания: (p∨q)→(¬r∨¬s).

Таблица истинности: p q r s (p∨q)→(r∨s) 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 Формула выполнимая (не общезначимая и не тождественно ложная). Число моделей формулы равно 13. д) Обозначения для простых высказываний: Животное является млекопитающим =p; Животное имеет острые зубы =q; Животное имеет клыки =r; Животное ест траву =s; Животное является хищником =t. Формула сложного высказывания: Формула выполнимая (не общезначимая и не тождественно ложная). Число моделей формулы равно 31.

Единственный случай ложности формулы соответствует ситуации, когда животное и млекопитающее, и имеет острые зубы, и клыки имеет, и травы не ест — а не хищник. 3. Преобразовать следующие формы в КНФ: Решение а) б) ¬(r∨q∨¬p)→¬(t→¬s)≡¬(r∨q∨¬p)→¬(¬t∨¬s)≡ ≡¬ 4. Записать на языке логики предикатов следующие утверждения. а) Для любых трех чисел, если их произведение – нечетно, то все три числа – нечетны. б) Ни одна женщина не является одновременно политиком и домашней хозяйкой. в) Некоторые женщины одновременно являются юристами и членами конгресса. г) Каждый второкурсник прочитал хотя бы одну книгу.

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

Решение а) Для любых трех чисел, если их произведение – нечетно, то все три числа – нечетны. ∀x ∀y ∀z ((P(x)∧P(y)∧P(z))→(Q(x⋅y⋅z)→(Q(x)∧Q(y)∧Q(z)))) Здесь: P(x)= «x является числом», Q(x)= «x нечетно». б) Ни одна женщина не является одновременно политиком и домашней хозяйкой. ∀x (P(x)→¬(Q(x)∧R(x))) Здесь: P(x)= «x — женщина», Q(x)= «x — политик», R(x)= «x — домашняя хозяйка». в) Некоторые женщины одновременно являются юристами и членами конгресса. ∃x (P(x)∧(Q(x)∧R(x))) Здесь: P(x)= «x — женщина», Q(x)= «x — юрист», R(x)= «x — член конгресса».

г) Каждый второкурсник прочитал хотя бы одну книгу. ∀x (P(x)→∃u (R(u)∧Q(x,u))) Здесь: P(x)= «x — второкурсник», Q(x,u)= «x прочитал u», R(u)= «u — книга». д) Кто-то встретил кого-то, а кто-то так никого и не встретил. (∃x(P(x)∧∃y (P(y)∧Q(x,y))))∧(∃x(P(x)∧∀y (P(y)→¬Q(x,y)))) Здесь: P(x)= «x является кем-то», Q(x,y)= «x встретил y». е) Каждое простое число, неравное двум, нечетно. ∀x (P(x)∧¬Q(x,2))→R(x) Здесь: P(x)= «x является простым числом», Q(x,y)= «x=y», P(x)= «x является нечетным числом». ж) Существуют числа, не имеющие общих делителей, кроме единицы. ∃x∃y (P(x)∧P(y)∧∀u ((P(u)∧Q(x,u)∧Q(y,u))→R(u,1)))

Здесь: P(x)= «x — число», Q(x,u)= «x делится на u», R(x,y)= «x=y».

з) Две прямые, каждая из которых параллельна третьей прямой, параллельны между собой. ∀x∀y ((P(x)∧P(y)∧∃u (P(u)∧Q(x,u)∧Q(y,u)))→Q(x,y)) Здесь: P(x)= «x — прямая», Q(x,y)= «x параллельно y». и) Судья Джонсон не восхищается ни одним жуликом. ∀x (P(x)→¬Q(судья Джонсон,y)) Здесь: P(x)= «x — жулик», Q(x,y)= «x восхищается y». к) Если по крайней мере один ученик решил все задачи, то каждую задачу решил по крайней мере один ученик. ∃x∀y ((P(x)∧Q(y))→R(x,y))→∀y∃x (P(x)∧Q(y)∧R(x,y))

Здесь: P(x)= «x — ученик», Q(y)= «y — задача», R(x,y)= «x решил y». л) В Москве живет женщина, имеющая брата в Петербурге, тогда и только тогда, когда в Петербурге живет мужчина, имеющий сестру в Москве. ∃x (P(x)∧Q(x,Москва)∧∃y(R(y)∧Q(y,Петербург)∧S(x,y)))↔∃x (R(x)∧Q(x,Петербург)∧∃y(P(y)∧Q(y,Москва)∧T(x,y))) Здесь: P(x)= «x — женщина», Q(x,y)= «x живет в y», R(x)= «x — мужчина», S(x,y)= «y является братом x», T(x,y)= «y является сестрой x». 5.

Указать все подформулы, а также области действия квантификации, свободные и связанные вхождения всех переменных в следующих формулах. а) S(t,w)∨∃x ∀w ((q(x,w)→P(x)→R(w)); б) (Q(x,y)↔∃y ∃z P(z,y))→(R(y)∨∀z Q(z)); в) ∃v ∃z P(z,v) & ¬Q(v,y)∨∀x ∃y (R(x)→T(x,y)); г) ∀x ∀u (¬S(u,x)∨R(x,u)∨Q(t))↔∃z ∃t P(x,t,z); д) (P(x,w)∨∃x ∀w (Q(x,w) & P(x,z)))→R(z,w). Решение а) S(t,w)∨∃x ∀w ((q(x,w)→P(x))→R(w)). Подформулы: S(t,w) ∃x ∀w ((q(x,w)→P(x))→R(w)) ∀w ((q(x,w)→P(x))→R(w)) (q(x,w)→P(x))→R(w) (q(x,w)→P(x)) R(w) q(x,w) P(x)

Областью действия квантора ∃x является формула ∀w ((q(x,w)→P(x))→R(w)), в этой формуле переменная x является связанной. Областью действия квантора ∀w является формула (q(x,w)→P(x))→R(w), в этой формуле переменная w является связанной. В подформулу S(t,w) переменные t и w входят свободно. б) (Q(x,y)↔∃y ∃z P(z,y))→(R(y)∨∀z Q(z)). Подформулы: Q(x,y)↔∃y ∃z P(z,y) Q(x,y) ∃y ∃z P(z,y) ∃z P(z,y) P(z,y) R(y)∨∀z Q(z) R(y) ∀z Q(z) Q(z)

Областью действия квантора ∃y является формула ∃z P(z,y), в этой формуле переменная y является связанной. Областью действия квантора ∃z является формула P(z,y), в этой формуле переменная z является связанной. Областью действия квантора ∀z является формула Q(z), в этой формуле переменная z является связанной. В подформулу Q(x,y) переменные x и y входят свободно, в подформулу R(y)∨∀z Q(z) переменная y входит свободно. Подформулы: ∃v ∃z P( ∃v ∃z P(z,v) ∃z P(z,v) P(z,v) T(x,y) Областью действия квантора ∃v является формула ∃z P(z,v), в этой формуле переменная v является связанной.

Областью действия квантора ∃z является формула P(z,v), в этой формуле переменная z является связанной. Областью действия квантора ∀x является формула ∃y (R(x)→T(x,y)), в этой формуле переменная x является связанной. Областью действия квантора ∃y является формула R(x)→T(x,y), в этой формуле переменная y является связанной. В подформулу ∃v ∃z P(z,v) ) переменная y входит свободно, в подформулу ¬Q(v,y) переменная v входит свободно. г) ∀x ∀u (¬S(u,x)∨R(x,u)∨Q(t))↔∃z ∃t P(x,t,z).

Подформулы: ∀x ∀u (¬S(u,x)∨R(x,u)∨Q(t)) ∀u (¬S(u,x)∨R(x,u)∨Q(t)) ¬S(u,x)∨R(x,u)∨Q(t) ¬S(u,x) S(u,x) R(x,u) Q(t) ∃z ∃t P(x,t,z) ∃t P(x,t,z) P(x,t,z) Областью действия квантора ∀x является формула ∀u (¬S(u,x)∨R(x,u)∨Q(t)), в этой формуле переменная x является связанной. Областью действия квантора ∀u является формула ¬S(u,x)∨R(x,u)∨Q(t), в этой формуле переменная u является связанной. Областью действия квантора ∃z является формула ∃t P(x,t,z), в этой формуле переменная z является связанной. Областью действия квантора ∃t является формула P(x,t,z), в этой формуле переменная t является связанной.

В подформулу ∀x ∀u (¬S(u,x)∨R(x,u)∨Q(t)) переменная t входит свободно, в подформулу ∃z ∃t P(x,t,z) переменная x входит свободно. R(z,w) Областью действия квантора ∃x является формула ∀w (Q в этой формуле переменная x является связанной. Областью действия квантора ∀w является формула Q(x,w в этой формуле переменная w является связанной. В подформулу P(x,w) переменные x,w входят свободно, в подформулу R(z,w) переменная w входит свободно.

Переменная z входит свободно во всю формулу. 6. Используя метод резолюций доказать невыполнимость (или выполнимость) следующих множеств дизъюнктов. Применять произвольный порядок перебора дизъюнктов, а также, по указанию преподавателя, одну из следующих стратегий: предпочтение одночленам, линейную, насыщение уровня. }. Решение а) {(q∨¬r),(¬q∨¬r),(q∨r),(¬p∨¬r),¬q}. 1) (q∨¬r),(q∨r)⊢q 2) q,¬q⊢∅ Множество дизъюнктов противоречиво (невыполнимо). б) {(p∨r),(p∨¬r),(¬p∨¬r),(q∨¬p∨¬r),¬p}; 1) (p∨r),(p∨¬r)⊢p 2) p,¬p⊢∅ Множество дизъюнктов противоречиво (невыполнимо). в) {(r∨¬q∨s),(¬q∨¬r∨¬s),(q∨¬s),s,¬r}; 1) (q∨¬s),s⊢q 2) q,(¬q∨¬r∨¬s)⊢(¬r∨¬s) 3) q,(r∨¬q∨s)⊢(r∨s) 4) (¬r∨¬s),s⊢¬r 5) ¬r,(r∨¬q∨s)⊢(¬q∨s) 6) (¬q∨s),q⊢s

Множество дизъюнктов непротиворечиво (выполнимо). г) {(q∨s∨¬p),(s∨¬q),(¬p∨¬s),(r∨¬p),p}; 1) (q∨s∨¬p),(s∨¬q)⊢(s∨¬p) 2) (s∨¬p),(¬p∨¬s)⊢¬p 3) ¬p,p⊢∅ Множество дизъюнктов противоречиво (невыполнимо). д) {(p∨r),(p∨¬r),(¬p∨¬r),(q∨¬p∨¬r),¬p}; 1) (p∨r),(p∨¬r)⊢p 2) ¬p,p⊢∅ Множество дизъюнктов противоречиво (невыполнимо). е) {(p∨s),(p∨r∨¬s),(r∨¬p∨¬s),(¬r∨¬s),s}; 1) s,(r∨¬p∨¬s)⊢(r∨¬p) 2) s,(p∨r∨¬s)⊢(p∨r) 3) (r∨¬p),(p∨r)⊢r 4) r,(¬r∨¬s)⊢¬s 5) ¬s,s⊢∅

Множество дизъюнктов противоречиво (невыполнимо). ж) {(q∨¬p∨¬r),(¬p∨¬q),(p∨q),(q∨r),¬q}. 1) (q∨r),¬q⊢r 2) r,(q∨¬p∨¬r)⊢(q∨¬p) 3) (q∨¬p),(p∨q)⊢q 2) ¬q,q⊢∅ Множество дизъюнктов противоречиво (невыполнимо). 7. Записать формально следующее рассуждение на языке логики высказываний и доказать его справедливость, используя метод резолюций. а) Посылки: Заработная плата возрастает только, если будет инфляция. Если будет инфляция, то увеличится стоимость жизни.

Заработная плата возрастает. Заключение: Стоимость жизни увеличится. б) Посылки: Если 2 — простое число, то это наименьшее простое число. Если 2 — наименьшее простое число, то 1 не есть простое число. Число 1 не есть простое число. Заключение: 2 — простое число. в) Посылки: Джон или переутомился или он болен. Если он переутомился, то он раздражается. Он не раздражается. Заключение: Джон болен. г) Посылки: Если завтра будет холодно, я надену теплое пальто, если рукав будет починен.

Завтра будет холодно, а рукав не будет починен. Заключение: Я не надену теплое пальто. д) Посылки: Если исход скачек будет предрешен сговором или в игорных домах будут орудовать шулеры, то доходы от туризма упадут и город пострадает. Если доходы от туризма упадут, полиция будет довольна. Полиция никогда не бывает довольна. Заключение: Исход скачек не предрешен сговором. е) Посылки: Или Сэлли и Боб одного возраста, или Сэлли старше Боба. Если Сэлли и Боб одного возраста, то Нэнси и Боб не одного возраста.

Если Сэлли старше Боба, то Боб старше

Уолтера. Заключение: Или Нэнси и Боб не одного возраста, или Боб старше Уолтера. Решение а) Простые высказывания: Заработная плата возрастает =p; Имеет место инфляция =q; Увеличивается стоимость жизни =r. Схема умозаключения: p→q,q→r,p⊨r Доказательство. Запишем посылки в эквивалентной форме как набор дизъюнктов (для чего выразим импликацию через дизъюнкцию и отрицание) и добавим к этому набору отрицание заключения. Получим набор дизъюнктов: {(¬p∨q),(¬q∨r),p,¬r}

Выведем из этого набора пустой дизъюнкт: 1) (¬p∨q),p⊢q 2) q,(¬q∨r)⊢r 3) r,¬r⊢∅ Из противоречивости множества дизъюнктов следует правильность умозаключения. б) Простые высказывания: 2 — простое число =p; 2 — наименьшее простое число =q; 1 не есть простое число =r. Схема умозаключения: p→q,q→r,r⊨p Доказательство. Запишем посылки в эквивалентной форме как набор дизъюнктов и добавим к этому набору отрицание заключения. Получим набор дизъюнктов: {(¬p∨q),(¬q∨r),r,¬p}

Попробуем вывести из этого набора пустой дизъюнкт: 1) (¬p∨q),(¬q∨r)⊢(¬p∨r) 2) (¬p∨r),r⊢¬p 3) (¬p∨r),¬p⊢r Пустой дизъюнкт в данном случае вывести нельзя. Умозаключение ошибочное. в) Простые высказывания: Джон переутомился =p; Джон болен =q; Джон раздражается =r. Схема умозаключения: p∨q,p→r,¬r⊨q Доказательство. Запишем посылки в эквивалентной форме как набор дизъюнктов и добавим к этому набору отрицание заключения. Получим набор дизъюнктов: {(p∨q),(¬p∨r),¬r,¬q}

Попробуем вывести из этого набора пустой дизъюнкт: 1) (p∨q),¬q⊢p 2) (¬p∨r),p⊢r 3) r,¬r⊢∅ Из противоречивости множества дизъюнктов следует правильность умозаключения. г) Простые высказывания: Завтра будет холодно =p; Я надену теплое пальто =q; Рукав будет починен =r. Схема умозаключения: p→(r→q),p,¬r⊨¬q Доказательство. Запишем посылки в эквивалентной форме как набор дизъюнктов и добавим к этому набору отрицание заключения. Получим набор дизъюнктов: {(¬p∨¬r∨q),p,¬r,q}

Попробуем вывести из этого набора пустой дизъюнкт: 1) (¬p∨¬r∨q),p⊢(¬r∨q) Резольвент больше нет. Пустой дизъюнкт вывести нельзя. Умозаключение ошибочное. д) Простые высказывания: Исход скачек предрешен сговором =p; В игорных домах орудуют шулеры =q; Доходы от туризма падают =r; Город страдает =s; Полиция довольна =t. Схема умозаключения: (p∨q Доказательство. Запишем посылки в эквивалентной форме как набор дизъюнктов и добавим к этому набору отрицание заключения.

Для этого проделаем вспомогательную работу — преобразуем первую посылку: Получим набор дизъюнктов: {(¬p∨r),(¬p∨s),(¬q∨r),(¬q∨s),(¬r∨t),¬t,p} Попробуем вывести из этого набора пустой дизъюнкт. 1) (¬p∨r),p⊢r 2) r,(¬r∨t)⊢t 3) t,¬t⊢∅ Из противоречивости множества дизъюнктов следует правильность умозаключения. е) Посылки: Или Сэлли и Боб одного возраста, или Сэлли старше Боба. Если Сэлли и Боб одного возраста, то Нэнси и Боб не одного возраста. Если Сэлли старше Боба, то Боб старше Уолтера.

Заключение: Или Нэнси и Боб не одного возраста, или Боб старше Уолтера. Простые высказывания: Сэлли и Боб одного возраста =p; Сэлли старше Боба =q; Нэнси и Боб не одного возраста =r; Боб старше Уолтера =s. Схема умозаключения: p∨q,p→r,q→s⊨r∨s Доказательство.

Запишем посылки в эквивалентной форме как набор дизъюнктов и добавим к этому набору отрицание заключения, которое распадается на два дизъюнкта: ¬(r∨s)≡¬r & ¬s. Таким образом, мы получили набор дизъюнктов: {(p∨q),(¬p∨r),(¬q∨s),¬r,¬s} Попробуем вывести из этого набора пустой дизъюнкт. 1) (p∨q),(¬p∨r)⊢(q∨r) 2) (q∨r),(¬q∨s)⊢(r∨s) 3) (r∨s),¬r⊢s 4) s,¬s⊢∅ Из противоречивости множества дизъюнктов следует правильность умозаключения.