Понимание доказательств истинности по отношению к таблицам доказательств
Я занимаюсь дискретными структурами и изучаю доказательства истинности и сортировку (ETC. ((A→B)∨B)→C, (¬p→q)⊕¬q и т. д., могу знать, как они работают и как прийти к ответ, однако в последнее время вещи, похожие на
A→B
B→C A∨¬B
B ¬A
____ ____
A→C ????
???
появились, и я не могу найти никакой информации об этом формате или о том, как его решить в Google, и мне не дали никакой информации об этом и о том, как его решить, как таковой. Он новый, и я не знаю, как к нему подойти. Ближе всего к аналогичному источнику, который я нашел, были книги Google по теории вычислений и учебникам по автоматам и алгебре, которые, казалось, ссылались на них как на матрицы. Я пытался делать каждую таблицу истинности отдельно, но не смог найти шаблон, чтобы связать ее.
Приветствуются источники или примеры того, как обращаться с такого рода доказательствами. Я никогда не сталкивался с этим макетом раньше, я вполне может быть что-то знаю, просто в новом формате. Спасибо за любую соответствующую помощь заранее.
Ответы 1
Есть два способа доказать вещи в логике:
- вычислив значение для всех входных данных, а затем проверив, что это тавтология
- используя систему доказательств, чтобы манипулировать формулами, чтобы показать, что это тавтология
Вы привыкли подходить к 1. Понятно и конкретно. Подход 2 более абстрактный и более сложный. Чтобы выполнить доказательства в системе доказательств, вы должны сначала исправить систему доказательств. Это означает провозглашение некоторых аксиом и правил логического вывода.
Например, можно найти простую систему здесь:
- А→(Б→А)
- (А→(В→С))→((А→В)→(А→С))
- (¬A→¬B)→(B→A)
- Дедукция по Modus Ponens: A, A → B | Б
В этой системе ваше доказательство может выглядеть так:
1. A→B, B→C, B | (A→(B→C))→((A→B)→(A→C)) (2)
2. A→B, B→C, B | (B→C)→(A→(B→C)) (1)
3. A→B, B→C, B | A→(B→C) MP on 2. and hypothesis B→C
4. A→B, B→C, B | (A→B)→(A→C) MP on 1. and 3.
5. A→B, B→C, B | A→C MP on 4. and hypothesis A→B
На каждом шаге вы либо вводите новый экземпляр одной из ваших аксиом, либо применяете правило дедукции для получения новой строки. С этого момента вы можете использовать строки, полученные таким образом, для получения новых строк, пока не получите желаемый результат.
Ваш второй не имеет большого смысла, поскольку вы не можете доказать то, что не было заявлено. Если вы получаете что-то подобное, я предлагаю вам просто заполнить пробел чем-то, что легко доказать, например true, а затем указать true в доказательстве и покончить с этим.