Томский межвузовский центр дистанционного образования
Томский государственный университет
систем управления и радиоэлектроники (ТУСУР)
Контрольная работа № 1
по дисциплине
«Математическая логика и теория алгоритмов»
автор учебного пособия:
Зюзьков В.М.
Выполнил:
Студент ТМЦДО
специальности 220201
Вариант №11
Перевести на формальный язык (обязательно указывая универсум):
«Некоторые лентяи на оптимисты, но жизнелюбы».
Универсум М ={люди}. Предикаты: L(x) ≡ «х – лентяй», O(x) ≡ «х – оптимист», Z(x) ≡ «х – жизнелюб».
Формула:
Перевести на формальный язык (обязательно указывая универсум):
«Два философа сидят за столом и спорят»
Универсум М ={люди}. Предикаты: F(x) ≡ «х – философ», S(x) ≡ «х – сидит за столом», С(x,y) ≡ «х спорит с y»
Формула:
Перевести с формального языка на человеческий:
(R – Множество вещественных чисел).
Перевод: Для любого вещественного числа есть большее, синус которого равен нулю.
Перевести на формальный язык (обязательно указывая универсум):
«Ни один судья не справедлив».
Универсум М ={люди}. Предикаты: J(x) ≡ «х – судья», S(x) ≡ «х – справедлив».
Формула:
Является ли формула
тавтологией?
Использовать метод доказательства от противного.
Тавтология – формула, истинная независимо от того какие значения принимают переменные входящие в неё. Соответственно нам необходимо доказать, что она не может быть ложной. Представим, что формула ложна при некотором сочетании переменных.
|
| |
| |
(подставили в формулы значения q, r и t ) |
Желая избежать противоречия примем , получим |
, противоречия нет. |
Получили значения переменных, при которых формула является ложной, следовательно, она опровержима и не являетсятавтологией.
При каких значениях переменных формула
ложна?
Переберём все возможные комбинации.
1. Из утверждения получаем, что и одновременно невозможно.
2. Из утверждения получаем, что и одновременно невозможно
3. Из утверждения получаем, что и одновременно невозможно
4. Возьмём и , получаем (верно), (верно), (верно).
выполняется.
Ответ: формула ложна только при и , других вариантов нет.
Является ли формула
тавтологией?
|
| |
| |
(подставили в формулы значения Л, r и t ) |
Так как и , то подставим и получим |
- противоречие. |
Пришли к противоречию, следовательно, исходная формула – тавтология.
Проверить, что и
Решение: Сначала следует попробовать опровергнуть это утверждение, т.е. найти такие множества A, B и C, чтобы выполнялось отношение , но не выполнялось и или, наоборот, выполнялось и , но не выполнялось . После безуспешных попыток найти такие множества следует доказать данное утверждение.
Доказательство распадается на два этапа.
Докажем сначала, что и . Пусть и выполнено, докажем, что . Поскольку требуется доказать включение множеств, то возьмем произвольный элемент , следовательно (из ), значит и тем более . Аналогично для .
Докажем теперь, что и . Пусть выполнено, докажем, что и . Поскольку требуется доказать включение множеств, то возьмем произвольный элемент , однозначно . Значит и тогда . Аналогично для B. Доказательство закончено.
Проверить, что
Это выражение верно, так как согласно не существует элемента , который не входил бы в . Следовательно, для , . Обратное не верно.
Проверить тождество
Решение. Построим диаграмму Эйлера для левого множества в четыре этапа.
Диаграмма для множества | Диаграмма для множества |
| |
Диаграмма для множества | Диаграмма для множества |
| |
Диаграммы Эйлера показывают, что тождество выполняется. Докажем это. Используя основные тождества алгебры множеств, преобразуем левую и правую части к одному множеству.
Преобразуем отдельно первое и второе множества.
Другие работы по теме:
Сущность неоклассической экономической теории
Неоклассическая экономическая теория возникла в 1870-е годы. Представители: Карл Менгер, Фридрих фон Визер, Эйген фон Бём-Баверк (австрийская школа), У. С. Джевонс и Л. Вальрас (математическая школа), Дж. Б. Кларк (американская школа), А. Маршалл и А. Пигу (кембриджская школа).
Структура философского знания
Характеристика и структура внутренней специализации философии, сущность ее основополагающих разделов: онтология, гносеология, логика, этика, эстетика и история философии. Роль и значение законов и принципов в становлении философского знания как системы.
Логика
Предмет логики, ее значение и виды. Особенности определения истинности сложного суждения по таблице истинности. Построение фигуры категорического силлогизма на основании посылки: "Все люди – смертны". Путь формирования логической культуры мышления.
Математическая логика
Ее еще называют символической логикой. Математическая логика - это та же самая Аристотелева силлогистическая логика, но только громоздкие словесные выводы заменены в ней математической символикой.
Многозначные логики
Обычная Аристотелева логика называется двузначной, потому что ее высказывания, имеют два значения, то есть они могут быть либо истинными, либо ложными. Однако мы знаем, что в реальности далеко не всегда можно определить точно истинность или ложность.
Диалектическая логика
Диалектическая логика (от греч. dialegomai — веду беседу) — филос. теория, пытавшаяся выявить, систематизировать и обосновать в качестве универсальных основные особенности мышления коллективистического общества.
Васильев Николай Александрович
Васильев Николай Александрович- логик, психолог, философ. Профессор Казанского университета с 1918. Предвосхитил конструктивизм в логике /неуниверсальность закона исключенного третьего/.
Программирование алгоритмов управления
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования
Теория вероятностей
Содержание Задание 1 Задание 2 Задание 3 Задание 4 Задание 5 Задание 6 Список используемой литературы Задание 1 Найти общее решение дифференциального уравнения первого порядка:
Математическая модель распределения информации
1 Математическая модель распределения информации Математическая модель системы распределения информации включает следующие три основных элемента: входящий поток вызовов (требований на обслуживание), схему системы распределения информации, дисциплину обслуживания потока вызовов.
Теория вероятностей
Общее решение дифференциального уравнения первого порядка. Уравнение с разделенными переменными. Выбор частного интеграла. Частное решение дифференциального уравнения второго порядка. Вероятность проявления события, интегральная формула Муавра-Лапласа.
Бинарные отношения
Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных и n-арных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется - геометрический аспект теории бинарных отношений есть попросту теория графов.
Возникновение и развитие символической логики
Возникновение и развитие символической логики связано с работами Г.Фреге (1848–1925) и Ч.С.Пирса (1839–1914). После того, как Фреге в 1879 и Пирс в 1885 ввели в язык алгебры логики предикаты, предметные переменные и кванторы, возникла реальная возможность построения системы логики в виде логического исчисления, что и было сделано Фреге, который по праву считается основателем символической логики в ее современном понимании.
Логика как самостоятельная наука
Введение Еще в древности люди знали, что достоверность выводных знаний зависит не только от истинности исходных посылок, но и от способа их соединения. Для того, чтобы убеждать, надо не только хорошо говорить, но и владеть различными приемами построения умозаключений и доказательств.
Тривиум
Введение 1 Состав 1.1 Грамматика 1.2 Риторика 1.3 Логика Список литературы Введение Тривиум, или тривий (лат. trivium — перекрёсток трёх дорог) — первая ступень средневекового образования, основа дальнейшего обучения. Предшествовала квадривиуму и состояла из трёх (отсюда название) дисциплин — грамматики, диалектики (логики) и риторики.
Рафаил Островский
(1963) является профессором факультета компьютерных наук и профессором факультета математики в Университете Калифорнии в Лос-Анджелесе . Он - известный учёный в области алгоритмов и криптографии [1]. Проф. Островский получил степень доктора философии (PhD) в 1992 году в Массачузетском Технологическом Институте.
Лейзерсон, Чарльз Эрик
Чарльз Эрик Лейзерсон — профессор, американский специалист в области компьютерных наук, информатики. Специализируется на теории параллельных и распределённых вычислений и частично — практическим её применениям. Работая в этом направлении, разработал язык программирования Cilk для многопотоковых вычислений, который использует один из лучших алгоритмов захвата задачи (англ. work-stealing) при планировании.
Лабораторная работа №7
Цель работы: Получение навыков реализации циклических алгоритмов с неизвестным числом повторений цикла, операторов цикла с предусловием и постусловием и итерационных циклических алгоритмов.
Лабораторная работа №5
Цель работы: изучение условного оператора, оператора отбора, составного оператора и правил программирования разветвляющихся алгоритмов. Задание № 17
Лабараторная работа №8
Цель работы: Получение навыков реализации циклических алгоритмов с неизвестным числом повторений цикла, операторов цикла с предусловием и постусловием и итерационных циклических алгоритмов.
Предмет и структура информатики
Б.В.Соболь Термин информатика получил распространение с середины 80-х гг. прошлого века. Он состоит из корня inform - «информация» и суффикса matics
Алгоритмизация и программирование 2
1. Имеется информация о наличии наименований продуктов на складе. Определить общее количество оборудования 1. Математическая постановка. а) Обозначение переменных.
Евгений Дюринг (During)
Евгений Дюринг (During) (1833–1921) – немецкий философ и экономист, профессор механики. Основные работы: «Курс философии» (1875), «Критическая история национальной экономии и социализма» (1875), «Логика и теория науки» (1878).