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).

3,555 questions
6 views

Part of the proof of the compactness theorem for propositional logic is trivial?

There's a proof of the theorem in Enderton's book wherein the second half serves as an exercise, stated as follows: Let $\Delta$ be a set of wffs such that (i) every finite subset of $\Delta$ is ...
59 views

Axioms of Propositional Logic with as few negation axioms as possible

Could you direct me to an axiom system for propositional logic over the connectives $\land$, $\lor$, and $\lnot$ with as few axioms over negation as reasonably possible? I've done a fair bit of ...
29 views

18 views

60 views

Prove propositional formula is a theorem

I need to show this formula is a theorem of propositional calculus. I tried assuming antecedent and proving consequent but didn't work for this proof. Do I need to show it is equivalent to true? How ...
69 views

Is this proof correct? Can you help me with this propositional logic exercise?

Problem: ~P Q v (R . P) /Q Answer: ~ P v ~ R 1, Add ~ (P . R) 3, De Morgan ~ (R . P) 4, Commutation Q 2, 5 Disjunctive Syllogism My textbook presents another ...
82 views

Proof of consistency of proof system syntactically.

I am trying to prove the "only one" part of the problem. Let $A$ be a set of propositional symbols, $\alpha$ ba a WFF over $A$ and $M\subseteq A$. And let $M^+: = M \cup \{(\neg a): a\in (A-M)\}$. ...
42 views

$((𝑃 \land \lnot 𝑄) \lor (𝑄 \land \lnot 𝑅)) \lor (\lnot 𝑃 \lor 𝑅) \equiv (\lnot P \lor (P \land \lnot Q)) \lor (R \lor (Q \land \lnot R))$ For the equivalence above, I am not sure how we get ...
74 views

Understanding ex falso quodlibet together with proof by contradiction in a Gentzen style ND Proof

I began studying some formal logic for possible future proof and type theory dives. I am at the very beginning, Gentzen style natural deductions. Some of these proof rules defies my intuition so I ...
24 views

48 views

32 views

24 views

How to determine a set of conclusions that can be derived from a set of premises?

Considering the following three premises. How is it possible to determine the set of conclusions that can be derived from the given set of premises. ...
26 views

How to use the distributive law correctly in propositional logic?

Can someone explain how in propositional logic these are equivalent : A ∧ B ∧ (¬B ∨ ¬C) ≡ A ∧ B ∧ ¬C Because using the distributive law I would get: ...
41 views

Using 0/1 instead of T/F in propositional logic. Is there any interest in doing so? ( either at the language level or at the metalogical level)

Is there any interest in using 0/1 instead of T/F in propositional logic? Does it allow things the T/F notation doesn't? Does it make easier or simplyfy in any way the exposition of logical theory?...
35 views

Is this Proof of (P→Q)→((Q→R)→(P→R)) based on Lukasiewicz Axiom System for CPL Correct?

Given Lukasiewicz axiom system for Classical Propositional Logic (CPL): (L1) α→(β→α) (L2) (α→(β→γ))→(α→β)→(α→γ) (L3) (¬α→¬β)→(β→α) and the usual Modus ...
14 views

Proving the following statements are equivalent

How would I be able to show that the following are equivalenet: a) x |= =| y (b) For all Γ, Γ |= x <-> Γ |= y (c) For all Γ and γ, we have Γ union {x} |= γ <-> Γ union {y} |= γ I can prove a ...
36 views

Prove by induction on structural complexity that the following set is complete

Consider the propositional language $L$ with denumerably many sentence letters $S_1,S_2,S_3,\ldots$ and the two connectives $\lnot,\lor$. Suppose that the set of sentences $\Gamma$ is a formal theory ...
32 views

How to prove this propositional tautology using only axioms from Mendelson's “Introduction to Mathematical Logic”

The result I wish to prove is (A -> (B -> C)) -> (B -> (A -> C)) Firstly does this have a name? I've been calling it "Swapping Hypothesis". ...
56 views

Natural deduction on exclusive OR

How do I formulate a natural deduction rule such that the conclusion is for example; a ∨ b (∨ being exclusive OR)
64 views

Syntactic use of “ false” . After “ false” can I write anything I want? ( Not a semantic question on “ ex falso sequitur quodlibet”)

If the proof below proof is correct, I'd like to know what is the name of the rule involving " false" that is used here. This question is not on " ex falso sequitur quodlibet". From false follows ...
47 views

How to transform a sequent notation to rule form?

I can write this proposition in sequent notation: $$(P\rightarrow Q)\rightarrow (\neg P \lor Q)$$ as this one in rule form (see here): $$\frac{(P\rightarrow Q)}{(\neg P \lor Q)}$$ But how can I ...
67 views

138 views

Why are there several axiom systems for propositional logic?

There is an axiom system that I found in Elliot Mendelson's, "Introduction to Mathematical Logic", p.27, and Theodore Sider's, "Logic for Philosophy", p.59: (A1) P->(Q->P) (A2) (P->(Q->P))->(P->Q)->(...