Записи с темой: математическая логика (список заголовков)
13:58 

Мат. логика, секвенциальное исчисление высказываний.

ackisha
I have diary now. Diaries are cool!
Добрый день. Есть следующее задание:
Если известно, что секвенции `\Gamma \rightarrow\Delta_{1} A\Delta_{2}` и `\Sigma_{1} A\Sigma_{2}\rightarrow\Pi` — аксиомы, доказать, что выводима секвенция
`\Gamma\Sigma_{1}\Sigma_{2}\rightarrow\Delta_{1}\Delta_{2}\Pi`. (`\Gamma, \Delta_{1}, \Delta_{2}, \Sigma_{1}, \Sigma_{2}, \Pi` — списки формул, A — пропозициональная переменная)

Что у меня уже получилось сделать:
1 случай: Пусть B — формула, входящая в `\Gamma` и секвенция `\Gamma\rightarrow\Delta_{1} A\Delta_{2}` является аксиомой "из-за" B. Тогда если B входит в `\Gamma`, то B входит либо в `\Delta_{1}`, либо в `\Delta_{2}`, тогда интересующая нас секвенция `\Gamma\Sigma_{1}\Sigma_{2}\rightarrow\Delta_{1}\Delta_{2}\Pi` выводима. При этом секвенция `\Sigma_{1} A\Sigma{2}\rightarrow\Pi` может являться аксиомой как "из-за" A, так и "из-за" другой переменной, входящей либо в `\Sigma_{1}`, либо в `\Sigma_{2}`
2 случай: Аналогично 1-му случаю, только теперь известно, что вторая секвенция является аксиомой не "из-за" A.

Что у меня сделать не получается: Доказать выводимость `\Gamma\Sigma_{1}\Sigma_{2}\rightarrow\Delta_{1}\Delta_{2}\Pi`, если обе исходные секвенции являются аксиомами "из-за" A. Не знаю даже, с какой стороны подойти.
Заранее спасибо за помощь!

@темы: Математическая логика

09:53 

Закономерность в числах

Прошу дать подсказку, кто сможет

Если
1*36=36,
8*23=23
8*67=1 , то 9*10=???

думаю, но не могу найти закономерность

@темы: Математическая логика

11:03 

Аксиоматическая теория множеств Цермело-Френкеля

Доброго времени суток!

Я пытаюсь изучать аксиоматическую теорию множеств. Решил начать с ZF как наиболее популярной. Вопросов значительно больше, чем ответов. Да и вопросы сформулировать, увы, здесь не всегда просто. Просто сплошная непонятность! Попытаюсь наиболее ясно сформулировать непонятные мне моменты.

I) В любой аксиоматической теории вводятся неопределяемые объекты и отношения между ними. Например, в евклидовой геометрии такими неопределяемыми объектами являются "точка", "прямая", "плоскость", "движение", а неопределяемыми отношениями - бинарное отношение "инцидентность" и тернарное отношение "лежит между" (согласно немного видоизмененной аксиоматике Гильберта, приведенной в книге Костина "Основания геометрии" () . В теории Пеано натуральных чисел неопределяемым объектом является "натуральное число", а неопределяемым отношением - бинарное отношение "следовать за". В связи с этим возникает вопрос. Какие неопределяемые понятия и отношения используются в аксиоматике ZF? С моей точки зрения, неопределяемыми понятиями должны быть "множества", "элементы", неопределяемыми отношениями - бинарное отношение "принадлежит" (∈ (), "равно" (=). Но если я прав (хотя, не похоже), почему тогда во всех аксиомах ZF используются только малые латинские буквы? Иначе говоря, почему на уровне букв не делается различия между "множествами" и "элементами"? В книге Н. И. Казимирова "Введение в аксиоматическую теорию множеств" на стр. 4 в первом абзаце утверждается: " В теории множеств (как в наивной, так и в формальной) мы любой объект считаем множеством, т. к., во-первых, это ничуть не мешает нам моделировать при помощи теории множеств реальные объекты, а во-вторых, это упрощает построение самой теории". Т. е. нет понятия "элемент" в аксиоматике ZF? Выходит, что элементами любого множества в ZF являются элементы, сами являющиеся множествами. Но тогда получается, например, следующее. Возьмем, к примеру, множество A, состоящее из числа 1: A={1}. Верным будет утверждение 1 ∈ A. Но 1 - само множество! Что ему тогда принадлежит? 1? Т. е. 1 ∈ 1? Так что ли поступают в аксиоматической теории множеств? (Напомню, что во многих учебниках по наивной теории множеств запись 1 ∈ 1 признается не имеющей смысла; верно лишь, что 1 {1}). Я заранее прошу прощения за большую выдержку из упомянутой книги Казимирова, но вот что он сам пишет по поводу такого странного положения дел:

"С самого начала мы предположили, что все множества, какие мы рассматриваем в наивной (канторовской) теории множеств представляют из себя произвольные наборы множеств, никаких других ограничений на понятие множества мы не накладывали. Покажем, что такое достаточно произвольное определение множества не может быть корректным с точки зрения логики, ибо приводит к противоречию. Следующий парадокс, который мы получим здесь, называется парадоксом Расселла.
Поскольку атомарная формула х у, выражающая принадлежность множества х к множеству у, имеет смысл для любых множеств х и у, ничто не мешает нам рассмотреть такой ее вид: х х. С точки зрения здравого смысла формула х х должна быть ложной для любого множества х, ибо мы считаем, что часть некоего объекта (в данном случае множества) не может совпадать с самим этим объектом. Поэтому мы вводим следующее определение: множество х такое, что х x, называется регулярным, а множество х, для которого хх, назовем сингулярным.
Снова нам ничто не мешает собрать все регулярные множества в одно множество R, точнее, R={x|x x}. Попытаемся теперь ответить на следующий вопрос: регулярно или сингулярно множество R?
Предположим, что множество R регулярно, т.е. R R. Но тогда R удовлетворяет тому свойству, которым оно само определено, значит, R R. Противоречие. Предположим тогда, что R сингулярно, т. е. R R. Но тогда R не удовлетворяет тому свойству, которым определены его элементы, следовательно, R R. Противоречие.
Итак, множество R не регулярно и не сингулярно, чего быть не может, если мы принимаем закон исключенного третьего (либо А, либо не А). Так может быть, R — не множество?
Полученный парадокс, как может показаться, доказывает несостоятельность самой идеи множества, как высшей точки абстракции в математических науках. На самом же деле весь тот путь, который мы прошли при построении множеств и при рассмотрении парадокса Расселла, уже дает предпосылки к решению этого парадокса. Мы с самого начала считали, что множество есть произвольная совокупность (множеств), что привело к построению парадоксального множества R. Насколько велико это множество, мы также не знаем, ибо мы предположили существование сингулярных множеств. С другой стороны, если предположить, что все множества регулярны, то R будет просто множеством всех множеств. Конечно, это не избавляет нас от противоречия, но зато дает повод попытаться исключить из рассмотрения сингулярные множества, а также «слишком
большие» совокупности множеств путем навязывания множествам некоторых условий или, как принято говорить, аксиом".

Но в нашем случае речь идет не о "больших множествах", а всего лишь о множестве, состоящем из одного элемента. И, по определению Казимирова, оно сингулярно! Итак, есть ли в теории ZF различие между "множествами" и "элементами"? Что-то уже много написал... Если кто-то поможет ответить, буду искренне признателен. Остальные вопросы в ходе дискуссии. Спасибо!




@темы: Математическая логика

18:25 

построить машину Тьюринга

Построить для функции f(x,y)=x, если x>y; y, если x<y; 0, если x=y
какая идея построения?

@темы: Дискретная математика, Математическая логика

15:44 

схоластика в импликации

вейко
что толку горевать?
читать дальше

безбожно долго размышлял над над таблицей истинности импликации

предположим A:= X>0 В:=X-1>0
эта эмпликация верна для х>1 на области действительных чисел, а для всей области верной не является и
выходит любое утвеждение может считаться верным пока не доказано обратное(презумпция невиновности)

также можно выделить утверждения которые являются обсюлютно верными на данной области (алгебраической структуре) A:= X>0 В:=X+1>0 (для действительных чисел)

и абсолютно ложными в том случае если нельзя выделить элемента где они выполняются
A:= X=0 В:=X-1>0

получается что ложные +верные в совокупности содержат в себе законы(аксиомы) алгебры(или даже в более широком смысле)
а безразличные (не абсолютные высказывания) формируют тело все возможных ситуаций ограниченых данными аксиомами

@темы: Математическая логика

19:56 

Функциональная сложность, примеры

blackhawkjkee
Здравствуйте.
Нужны примеры(желательно с решением) на определение функциональной сложности. Преподаватель сегодня спросил какую функциональную сложность имеет `a^n`. Ответить я не смог и препод немного упростил задание, спросив какая функциональная сложность `a^8`. Я не знал как ответить на такой вопрос, и в итоге он расписал все это дело так:
`a*a = a^2`
`a^2 * a^2 = a^4`
`a^4 * a^4 = a^8`
Сложность = 3.

Тут я понял что чего-то не понимаю, так как тот материал про функциональную сложность, который читал я, не очень помог мне в решении примера учителя. Материал был взят из учебника, который я еле-еле нашел. В интернете почему-то вообще нет подробной информации по этой теме. Может как-то по-другому формулируется, другие ключевые слова надо вводить?
В общем, прошу вашей помощи.

@темы: Математическая логика

23:06 

Dead Channel
I think its gonna rain
Здравствуйте.
Если не сложно, объясните, пожалуйста, на пальцах метод резолюций в логике высказываний.
Как я понимаю для использования этого метода необходимо выполнить следующее: строится сложная формула для исходного рассуждения(посылки из которых следует заключение). Это и будет являться теоремой, которую нужно доказать.
Затем к посылкам добавляется отрицание заключения и все это записывается в виде {посылка1, посылка2, ... , отрицание заключения}, после чего посылки, если это сложные высказывания, приводятся к кнф.
Теперь целью является вывод пустого дизъюнкта из данной формулы, что сводится к последовательному поиску контрарных пар (например, P и неP) в каких-либо двух дизъюнктах, в результате чего образуется резольвента этих дизъюнктов, содержащая все элементы этих двух дизъюнктов за исключением контрарной пары. Резольвента добавляется к формуле и так до тех пор, пока в скобках не обнаружатся два идентичных высказывания, резольвентой которых будет пустой дизъюнкт. Это, если я не ошибаюсь, и будет доказательством противоречивости(невыполнимости) формулы, а теорема считается доказанной, то есть из посылок действительно следует данное заключение.
Алгоритм действий я, кажется, улавливаю, но вот их смысл нет.
К тому же, есть и другие способы проверки правильности рассуждений, такие как построение таблиц истинности, преобразование формулы к тождественно истинной или метод от противного. Чем данный метод так принципиально выделяется?

@темы: Математическая логика

06:25 

Алгоритм Дейкстры

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

@темы: Дискретная математика, Математическая логика, Теория графов

23:56 

Dead Channel
I think its gonna rain
Здравствуйте.
Подскажите, что можно почитать про использование диаграмм Эйлера-Венна в логике предикатов? Ничего конкретного не гуглится.

@темы: Математическая логика

10:28 

Исчисление предикатов

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

@темы: Посоветуйте литературу!, Поиск книг, Математическая логика, Литература, Дискретная математика

18:03 

Математическая логика.

Добрый вечер, не проходили тему, а в экзаменационных билетах есть.
Не могли бы объяснить?
Задание : Найдите все неравносильные между собой формулы F(x, y), в которых:
F(x, y)<-> x = x*y.
Заранее спасибо!

@темы: Математическая логика

09:18 

Помогите с решением.

Пусть S(x, y, z) и П(x, y, z) соответственно предикаты сложения(z является суммой x и y) и умножения (z является произведением x и y), рассматриваемые на множестве Z всех целых чисел и на множестве N0 = N 'знак объединения' {0} целых неотрицательных чисел. Какой смысл имеют следующие формулы и на каком множестве (Z или N0) они истинны?
Формула (AAy)(EEx)S(x,y,0)
Заранее благодарю за помощь

@темы: Математическая логика

23:53 

ZFC

Система аксиом Цермело—Френкеля является интерпретацией языка первого уровня с равенством. В исходные символы данного исчисления входит бесконечный перечень индивидных переменных которые в интерпретации ZFC называются множествами.
Кроме символов исчисления в ZFC есть ещё 1 символ - ∈ и формула x ∈ y значит, что множество х является элементом множества у.
Таким образом, элемент некоторого множества - это множество, т.е. у нас нет разделения на множества и элементы множеств.
Элементами множества натуральных чисел являются 1, 2, 3,... и как я написал выше, они также являются множествами. Но что включают в себя эти множества? (Ведь не могут они быть пустыми, т.к. пустое множество единственно) Что отличает множество 2 от множества 1?

@темы: Математическая логика, Множества

18:01 

Математическая логика.

Помогите пожалуйста.

1. Докажите, что имеет место следующая выводимость, построив соответствующий вывод из гипотез

¯G |-> ( F v G) -> F

2. Проделайте доказательство теоремы о дедукции в следующей частной формулировке

Если ¯G |-> (F v G) -> F, то |-> F -> (( ¯G -> F) -> (G -> F))

3. Используя теорему о дедукции, докажите, что справедливы следующие выводимости

|-> (F -> G) -> (( ¯F -> G) -> G)

@темы: Математическая логика

09:43 

Доброе время суток! Одно из заданий по Математической логике и теории алгоритмов.
Пожалуйста подскажите как решить именно эту задачу, другие похожие задания уже решал.
Пусть U – множество точек плоскости. Рассмотрим два предиката.
B(a,b,c) - точки a,b,c –лежат на прямой, причем b между a и c.
D(a,b,c,d) – расстояние |ab| равно |cd|.
Выразить предикат тупого угла abc.

@темы: Математическая логика

18:55 

Математическая логика

pemac
Математическая логика
Ершов Ю.Л., Палютин Е.А.
Количество страниц: 356 стр.
Год издания: 2011
Формат: Djvu

rusfolder.com/42623834



В книге изложены основные классические исчисления математической логики: исчисление высказываний и исчисление предикатов; имеется краткое изложение основных понятий теории множеств и теории алгоритмов. Ряд разделов книги - теория моделей и теория доказательств - изложены более подробно, чем это предусмотрено программой. Для студентов математических специальностей вузов. Может служить пособием для специальных курсов. Рекомендовано УМС по математике и механике УМО по классическому университетскому образованию РФ в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям и специальностям : "Математика", "Прикладная математика и информатика", "Механика".

@темы: Литература, Математическая логика

13:57 

Машина Тьюринга

Пухлощекий_Страдалец
Счастье в секундах - маленьких, острых, щедрое к детям и скупое для взрослых...
Построить машину Тьюринга, применимую для всех слов `x_1x_2..x_n`в алфавите {a, b} и переводящую их в слово `alpha`.

`alpha` = bab, если слово начинается на ab, и `x_1x_2` в других случаях.

у меня вышло так:

Проверьте, пожалуйста, правильно ли.



@темы: Математическая логика

13:34 

Задача по матлогике

Пухлощекий_Страдалец
Счастье в секундах - маленьких, острых, щедрое к детям и скупое для взрослых...
Проверить корректность рассуждения:
"Если кража совершена "по наводке", то у преступника был сообщник, а если был сообщник, то налицо преступная группа. Если же преступление совершенно группой, то это - преступление с отягчающими обстоятельствами. Значит, если кража совершена "по наводке", то она - с отягчающими обстоятельствами.
Пусть, А - у преступника есть сообщник
В - кража совершена "по наводке"
С - есть преступная группа
D - преступление с отягчающими обстоятельствами.
Я составляла таблицу истинности, но препод сказал, что это неправильно.
У меня было так :B->A->C->D и B->D
и для этих двух выражений сравнивала полученные значения.
А как надо сделать?

@темы: Математическая логика

22:56 

Как избавиться от отрицания? `bar(x) cap bar(y)`

@темы: Математическая логика

20:21 

Обьясните, пожалуйста, как это решать
Пусть S(x, y, z) и П(x, y, z) соответственно предикаты сложения
(z является суммой x и y) и умножения (z является произведением x и y), рассматриваемые на множестве Z всех целых чисел и на множестве N0 = N  {0} целых неотрицательных чисел. Какой смысл имеют следующие формулы и на каком множестве (Z или N0) они истинны?  yx П(x, y, -x)

@темы: Математическая логика, Дискретная математика

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная