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
1answer
38 views

What are meta-level and object-level proofs?

I am reading "handbook of knowledge representation" and here the author mentioned two kinds of proofs for propositional logic: Meta-level and object-level proofs. It says: When we want to establish ...
0
votes
2answers
51 views

Equivalence condition of consistency of the system

I read the following statement in my modal logic book. Propositional calculus system $L$ is consistent if and only if for every proposition symbol $p$ in $L$, $\not\vdash p$ I wonder how to prove ...
1
vote
1answer
23 views

Negation Normal Form and the length of formulas

Consider propositional logic over the connectives $\land$, $\lor$, and $\lnot$. We have two well-formed formulas $\varphi$ and $\sigma$ which are equivalent: $\varphi \leftrightarrow \sigma$. The ...
0
votes
0answers
39 views

Completeness theorem in propositional logic implies the compactness theorem

I would like some help with proving the compactness theorem in propositional logic using the completeness theorem, that is: Given that every wff is a tautology iff it is a theorem, prove that a set $\...
5
votes
3answers
5k views

Explain the Absorption Law

I am currently in a Discrete Math class and reviewing some of my terminology and I don't really understand the Absorption Law. I am not looking for a proof or a truth table but an explanation in ...
6
votes
6answers
881 views

Simplify, equivalent for (p ∨ ¬q) ∧ (¬p ∨ ¬q)

In my text book I'm asked to deduce a simpler expression for (p ∨ ¬q) ∧ (¬p ∨ ¬q) Looking at an equivalency table I did, it seems p ∨ ¬q gives the same results as ...
4
votes
1answer
147 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 \to (Q \to P)$ (A2) $(P \to (Q \...
0
votes
2answers
955 views

Write expressions using only NAND operator and prove logically equivalent?

It can be shown that ~$p \equiv (p \uparrow p)$ and $p \wedge q \equiv (p \uparrow q) \uparrow (p \uparrow q)$. You don’t need to show these. However, write the expressions $p \to q$ and $p \vee q$ ...
0
votes
0answers
9 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 ...
0
votes
1answer
1k views

Difference between Universal Quantification and Existential Quantification (Restricted Domain)

Question Title may seems similar but Its not a Duplicate Question. Question:- Suppose I want to formulate a statement "All Apples are Delicious. Let F be the domain of fruits and A(x) : is an ...
2
votes
1answer
61 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
28 views

Understanding Frege/Hilbert axioms of propositional logic [closed]

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 ...
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^¬...
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 ...
1
vote
3answers
59 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 ...
0
votes
3answers
71 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 ...
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 ...
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, $...
3
votes
2answers
86 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 ...
2
votes
1answer
85 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
3answers
75 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 ...
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 $\...
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 ...
8
votes
4answers
656 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
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 ...
11
votes
4answers
53k views

Find DNF and CNF of an expression

I want to find the DNF and CNF of the following expression $$ x \oplus y \oplus z $$ I tried by using $$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$ but it got all messy. I also ...
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 ...
1
vote
3answers
49 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
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 ∨ (𝑝 → ...
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\...
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 ...
3
votes
2answers
309 views

Propositional Calculus and “Lazy evaluation”?

I want to formalize a system, and currently I don't know, if I can use propositional calculus in my case. At first, I though that I need a simple conjunction. $A \wedge B$ However, there is a ...
1
vote
1answer
39 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
vote
1answer
33 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 \...
-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
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: ...
0
votes
1answer
33 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". ...
3
votes
3answers
68 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 ...
-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?...
0
votes
3answers
43 views

Please explain (p ∧ q) --> r and what the correct method to work this out is

I understand P ∧ Q, being that both must be equivalent, ie True & True, or False and False. I understand P --> Q implies that if P is True we know what Q is and if Q is true then the result is ...
-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 ...