Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
3answers
29 views

Is $([P \wedge (\sim Q)] \Rightarrow Q) \Rightarrow P \vdash P$ a theorem in propositional logic?

By constructing truth tables, I have found that $([P \wedge (\sim Q)] \Rightarrow Q) \Rightarrow P \vdash P$. In attempting to prove it, so far I have: $1 \: (1) \: ([P \wedge (\sim Q)] \Rightarrow ...
1
vote
0answers
27 views

Understanding Frege/Hilbert axioms of propositional logic [on hold]

I recently came across a description of Frege's propositional calculus. It consists of six axioms and one rule of inference, described here. Hilbert's deductive system is similar. Frege's six axioms ...
0
votes
1answer
16 views

Probability with logical conditional instead of conjunction

I think I caught a mistake in the wording of a problem on my instructor's exam: The question: $Prob$(if the card is not a face card, then it is divisible by 3) The question however was graded as ...
0
votes
0answers
29 views

Complete distributivity in infinitary propositional logic

Let $\mathcal{L}$ be an infinitary language of propositional logic built up on $\omega_1$ distinct sentential variables and allowing the formation of disjunctions and conjunctions of all lengths less ...
1
vote
2answers
51 views

Simplifying propositional formula

[a ^ ¬(b^c^d)] V [a^b^ ¬(c^d)] V [¬a^b^¬(c^d)] V [a^b^¬c^d] V [a^b^c^¬d] =[a^¬(b^c^d)] V [b^¬(c^d)] V [a^b^¬c^d] V [a^b^c^¬d] =[a^¬(b^c^d)] V [b^¬c] V [b^¬d] V [a^b^¬c^d] V [a^b^c^¬d] =[a^¬b] V [a^¬...
1
vote
3answers
55 views

How do we distinguish between (logical) axioms and other assumptions of a proof?

While I was studying Propositional Calculus from Elliott Mendelson's book of Introduction to Mathematical Logic, in the section of Formal Theory I came across a notation $\Gamma$ that represents a set ...
1
vote
1answer
26 views

Name for this family of operations

Given some True / False propositions $A,B,C,D, \dots$ I would like to know if there is a name for these operations: $ONE(A,B,C)$ - true if exactly one of $A, B$ and $C$ is true, false otherwise $TWO(...
1
vote
1answer
18 views

Propositional logic and probabilities

I have four propositions $A, B, C, D$ each of which is either true or false. These statements are completely arbitrary and have no relation to each other. Is it logically sound to make the statement, $...
0
votes
3answers
67 views

Tautology with Natural Deduction

I'm trying to prove (p->q) v (q->p) is a tautology. I need to start with an assumption, I would start with p->q or q->p but I always get stuck in the assumption. I don't find any way to get out of it ...
3
votes
2answers
82 views

Natural Deduction Proof for Modus Tollens

Suppose I would like to proof modus tollens, i.e. $P\ \to Q,\ \lnot Q\ \vdash\lnot P$, based on Gentzen-style natural deduction for classical logic. Using rules of inference for NK as given in ...
0
votes
0answers
14 views

Implication and conclusion in propositional calculus

Let A and B be any propositions expressible in the propositional calculus notation. Show that A $\vdash$ B is provable by the rules of propositional calculus if and only if it is provable that $\...
0
votes
1answer
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 ...
2
votes
3answers
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 ...
2
votes
1answer
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)\}$. ...
3
votes
2answers
42 views

Could provide some further detail about this step in a proof

$((𝑃 \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 ...
3
votes
3answers
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 ...
3
votes
1answer
24 views

Is this CNF equivalent correct?

I am reading Wolf’s A Tour Through Mathematical Logic. In Section 1.2, Propositional Logic, he gives the following example: Example 6. The statement $ \mathsf{[(P\rightarrow\neg Q)\leftrightarrow (...
0
votes
1answer
38 views

Find which formulas are equivalent to a given propositional formula

The following problem was given during a quiz. I think there is a mistake because of the number of parenthesis. There is an extra or missing parenthesis (i.e there are 7 parenthesis). The teacher said ...
0
votes
1answer
71 views

Prove (de Morgan 1) $\vdash A\wedge B \equiv \neg (\neg A \vee \neg B)$

Proof - starting from the right side: $$\neg (\neg A \vee \neg B)$$ $<=>\text{(axiom: introduction of }\neg \text{)}$ $$\neg A \vee \neg B \equiv \bot $$ $<=> (\text{Leib + }\vdash\neg A\...
1
vote
3answers
48 views

Does this propositional logic equivalence touching inplication have a name : ( (A&B) -> (A&C) ) <-> (A -> (B->C) )?

Stanford truth table generator tells me that the following formula is a tautology: $\left(\left(A\land B\right)\Rightarrow\left(A\land C\right)\right) \Leftrightarrow \left(A\Rightarrow\left(B\...
0
votes
1answer
50 views

Proof by contradiction to prove that (√10)/2 is an irrational number

I'm struggling with a textbook question thats asks to use proof by contradiction to show that (√10)/2 is an irrational number. I tried following a similar proof that the teacher did in class, but I ...
0
votes
1answer
36 views

Logical equivalences - show argument is valid

Using only the rules of inference and the logical equivalences, show that the following argument is valid. You may assume that all the premises given are true. Premises: 𝑢 ∧ 𝑡 𝑟 → 𝑞 s ∨ (𝑝 → ...
-1
votes
0answers
34 views

Propositional Logic; Problem: Tautologies and Contradictions

I have this task which I am stuck with trying to solve it. I am aware of the fact that the truth table would always yield a "false" in the last column in case of a contradiction, and always a "true" ...
0
votes
0answers
23 views

Show that $\Gamma \vDash_{taut} B \leftrightarrow \Gamma \cup \{\lnot B\}$ is unsatisfiable.

I'm going through an example proof, and I'm unclear why it's important to write: Let $\Gamma \cup \{\lnot B\}=A_1,...A_n,\lnot B$, why not let $\Gamma \cup \{\lnot B\}=\lnot B$. By definition of $\...
1
vote
1answer
32 views

Show that $A_1,…,A_n\vDash_{taut} B \leftrightarrow \vDash_{taut} A_1 \to A_2\to …\to A_n\to B$

I'm having a hard time understanding the iff part of this proof by induction (is this vacuously true?), below is my attempt: Base Case: Let $n = 1$, therefore $A_1\vDash_{taut} B \leftrightarrow \...
8
votes
4answers
641 views

Is there a general effective method to solve Smullyan style Knights and Knaves problems? Is the truth table method the most appropriate one?

Below, an attempt at solving a knight/knave puzzle using the truth table method. Are there other methods? Source : https://en.wikipedia.org/wiki/Knights_and_Knaves
1
vote
1answer
38 views

What is the relationship between propositional calculus, set theory, and Boolean algebra?

The connective $∧$ (conjunction) in propositional logic is essentially the same as ∩ (intersection) in set theory if one thinks of 'false' as 'not a member' and 'true' as 'a member'. De Morgan's laws, ...
-1
votes
3answers
76 views

Can “and” be Substituted with “+” in proofs

Notes: Considering two limit were given $$\mathop {\lim }\limits_{x \to a} f\left( x \right) = L \hspace{0.1in} and \hspace{0.1in} \mathop {\lim }\limits_{x \to a} g\left( x \right) = M$$ means ...
0
votes
1answer
19 views

Converting from formula to clause

I'm trying to refresh myself on the subject. If φ= (L1 ∨...∨ Ln) whereL1,...,Ln are literals, then{L1, ..., Ln}is the clause associated to φ. How would I convert ¬(¬P ∨ Q) to a clause?
0
votes
1answer
46 views

Equivalence Between Law of Excluded Middle and Self-Implication

We know that $P \to Q$ is equivalent to $\neg P \lor Q$, as can be verified easily in truth table. Now suppose we have proof for self-implication below [the axiom system is Lukasiewicz's, with L1: $P ...
0
votes
1answer
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. ...
2
votes
2answers
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: ...
-1
votes
3answers
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?...
-1
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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". ...
2
votes
3answers
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)
0
votes
3answers
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 ...
0
votes
1answer
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 ...
3
votes
3answers
67 views

Natural deduction proof: $C, (C \land D)↔F \vdash (D \land E) \to F$

I'm having trouble with proving C, (C Λ D) ↔ F |- (D Λ E) → F If it were $\lor$ instead of $\land$, then I would be able to do it. If I can prove that $(C ...
2
votes
1answer
36 views

How to derive ~ ( P&Q) from ~ P using natural deduction?

Certainly if P is false, (P&Q) cannot be true. But how to prove this using natural deduction? I'd propose as a direct proof the following derivation : (1) ~P ( Premise ) (2) ~P v ~Q ( ...
1
vote
2answers
33 views

Logical Equivalences with English Statements

Showing two statements $p$ and $q$ are logically equivalent is to show $p \Longleftrightarrow q$. I understand this, however I think when looking at english statements showing whether or not they are ...
0
votes
1answer
33 views

Usage of adjective and imperative in statement logic

I think I know how to form sentences in statement logic if it's an "if statement" like (A) and (B) below, but how do I express adjective like "not so easy" or imperative like "Choose X or Y", as shown ...
0
votes
1answer
68 views

How to prove $\vdash p\to\neg\neg p$ in this system?

I was asked to prove $\vdash p\to\neg\neg p$ in this system. Axioms: $(\mathcal A_1)\vdash p\to(q\to p)$ $(\mathcal A_2)\vdash (p\to(q\to r))\to((p\to q)\to (p\to r))$ $(\mathcal A_3)\vdash \...
4
votes
1answer
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)->(...
0
votes
0answers
16 views

Graph Coloring in Propositional Logic

Let G be a legally colored graph with k colors; this means that each two adjacent vertices have different colors, and the total number of colors in G is k. In addition, the edges of the graph are ...
0
votes
1answer
38 views

Is the “ contrapositive relation” rigorously symmetric? What is rigorously the contrapositive of : ~X --> ~ Y?

Is the relation " being the contrapositive of" really symmetric? I mean : the contrapositive of X --> Y is ~Y --> ~X. If the relation " being the contrapositive of " is symmetric, then I can say ...