# 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,559 questions
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 ...
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 ...
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 ...
39 views

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$ ...
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 ...
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 ...
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 ...
29 views

18 views

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 ...
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
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 ...
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 ...
24 views

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 ∨ (𝑝 → ...
71 views

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" ...
23 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: ...
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". ...
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 ...
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?...
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 ...