Questions tagged [propositional-calculus]
Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).
5,579
questions
0
votes
1
answer
55
views
What is a statement in Chiswell & Hodges Mathematical Logic?
I am beginning to read Mathematical Logic by Chiswell and Hodges. In Chapter 2 Informal Natural Deduction, the authors don’t give a definition of statement. They say to use a test. I’m confused why ...
- 107
0
votes
0
answers
43
views
Proof of ((A→B)→A)→A using axioms and hypothetical syllogism
Problem:
Prove
(
(
𝐴
→
𝐵
)
→
𝐴
)
→
𝐴
((A→B)→A)→A using axioms and hypothetical syllogism (HS).
Relevant Axioms:
Axiom 1 (A1):
𝐴
→
(
𝐵
→
𝐴
)
Axiom 2 (A2):
(
𝐴
→
(
𝐵
→
𝐶
)
)
→
(
(
𝐴
→
𝐵
)
→
(...
- 21
3
votes
2
answers
66
views
Predicate formula of proposition, author lacks precision in explanations
I have a problem: Consider the two following propositions:
All persons have a mother.
There is one mother of all persons.
Now consider the predicate formulas of both propositions:
$\forall x \...
- 41
-1
votes
1
answer
62
views
Example of undecidable recursive set of formulas in Propositional Logic
Context
In first order logic, we study a lot various undecidable theories like Robinson arithmetic or Peano arithmetic. I was wondering what is there to study in the field of (un)decidability in the ...
- 29
1
vote
1
answer
63
views
Using contradiction to validate an argument
In general, when we want to establish the validity of the argument $(p_1 \land p_2 \land ... p_n ) \rightarrow q$, we can establish the validity of the logically equivalent argument $(p_1 \land p_2 \...
user1344875
0
votes
0
answers
108
views
Why can't three-valued logic (ternary logic) simply have only two truth values?
Consider the statement:
P ∧ ¬P ⊢ Q
where:
P is any proposition.
-¬P is the negation of P.
Q is another proposition.
Wouldn't proving both P and ¬P to be true simply lead to a new proposition Q, ...
- 9
0
votes
0
answers
32
views
A generalized algorithm to convert a formula in algebraic normal form to an equivalent formula that minimizes the number of bitwise operations
In this question, “bitwise operation” means any operation from the set {XOR, AND, OR}. The NOT operation is not included because ...
- 922
0
votes
0
answers
52
views
Would this logic be considered constructive?
I have asked about similar logics before, but this one is different.
The logics that I’ve asked about in the past take the Gödel-McKinsey-Tarski translation for Intuitionistic Propositional Logic to ...
- 1,328
-3
votes
0
answers
65
views
Justifying a swap from (mathematical) implication to material conditional and whether the antecedent of equivalence operator is assumed to be true
Suppose I would like to prove the Pigeonhole Principle using a Proof by Contradiction.
The Pigeonhole Principle states that if s objects are placed in k boxes for $s>k$, then at least one box ...
- 219
2
votes
1
answer
41
views
Understanding a proof of the completeness Theorem for Propositional Resolution.
I'm having trouble understanding the proof of 1.3.4., the Completeness Theorem for Propositional Resolution in this book.
The main portion of the proof goes like this:
Given a (finite) set of clauses ...
- 219
0
votes
0
answers
44
views
Propositional calculus - variable assignment proof
I am having trouble to formally prove the following:
let α,β,γ be well formed formulas.
prove that if Var(α) ∩ (Var(β) ∪ Var(γ)) = ∅ and β(α/p1)=γ(α/p1) then β=γ
It would be great to get some ...
-1
votes
1
answer
35
views
Given a formula how can we figure out if it is CNF or DNF
Can anyone please help me understand if the following formulas are DNF, CNF, both CNF and DNF, and neither CNF nor DNF? From my understanding, CNF is a conjunction of disjunction literals and DNF is a ...
2
votes
1
answer
35
views
Generate as short as possible boolean formula from a given truth table
Given a truth table, maybe 3-vars, 5-vars or even 10-vars, i can write its formula in DNF or CNF, and simplify it using K-Map or Quine-McCluskey algorithm. But it is based on {NOT, AND, OR}.
Now the ...
0
votes
1
answer
72
views
Confusion on Question from Kenneth Discrete Math Textbook
Suppose there are signs on the doors to two rooms. The sign on the
first door reads “In this room there is a lady, and in the other one
there is a tiger”; and the sign on the second door reads “In one ...
- 853
1
vote
1
answer
93
views
Substituting propositional variables given a true biconditional
Say I know that $p ↔ q$ AND $q ↔ (p ∧ ¬q) ∨ (¬p ∧ q)$ are both true. From hypothetical syllogism, the logical equivalence $(x → y) ∧ (x → z) ≡ x → (y ∧ z),$ and the simplification $(x ∧ y→ y$ is a ...
- 853