# 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,554 questions
16 views

### How would you use predicate logic to check if a statement is true or false?

Let $P(x,y,z)$ be the predicate $x+y<z$. Over which set is the statement $∀z∃x∃y\ P(x,y,z)$ true? $\Bbb Z^+=\{1,2,3,\dots\}$ or $\Bbb Z$? I had thought that it would be neither, but that ...
60 views

### What does the negated double turnstile ($\not\models$) mean?

I understand that the expression $\models \phi \rightarrow \psi$ means that $\phi \rightarrow \psi$ is a tautology. But what does the expression $\not\models \phi \rightarrow \psi$ mean? Does it mean ...
17 views

### Propositional Logic - Logical Simplification

Can we further simplify this statement. $\text{~a$\rightarrow$(b$\oplus$c)}$ I got around here and stuck. $\text{~a$\rightarrow$~[(b$\rightarrow$c)$\land$(c$\rightarrow$b)]}$ $\text{~a$\...
25 views

### About provability of modal axioms in modal logics

Suppose I'm asked to prove that one specific axiom from the list T, 4, B, D, 5 is not provable in some modal logic (KT, K4, KB, KD, K5, S4, S5, etc.). To be specific, suppose I'm asked to prove that 4 ...
50 views

### Proving that a sentence is inconsistent [duplicate]

I'm trying to understand if the sentence $\square\bot\land \phi$ is consistent in KD. I don't think it is true because it looks like no serial model where this sentence is satisfiable exists. As I ...
44 views

48 views

### Prove $\vdash \neg(\square F\land p)$ in $KD$

How to prove that $\vdash \neg(\square F\land p)$ in $KD$? The allowed rules are natural deduction rules and the axiom $\square p\to\diamond p$ where $\diamond p=\neg\square\neg p$. I actually don't ...
49 views

### Intuitionist Logic Question [duplicate]

Show that it is not the case that if ⊨ ¬(A ∧ B) then ⊨ ¬A or ⊨ ¬B. Consider the formula ¬(p∧¬p). Replace A with p and B with ¬p. Validity: this is deﬁned as truth preservation over all worlds of ...
20 views

### Is it possible to prove that propositional calculus is consistent using only its syntax?

Let us consider Gentzen's propositional calculus with only one axiom: $$\phi \vdash \phi$$ and 12 rules of inference. As far as I know this PC is consistent, i.e. not all of their expressions (...
44 views

### General rule for $(A \land B) \lor (\neg A \land D)$

I encountered the following small expression: $$(n\ge0\land y \gt 5) \lor(n \lt 0 \land x > 10).$$ The answer should be easily $(x > 10 \land y \gt 5)$ but unfortunately I don't see how ...
33 views

### Minimize term without Karnaugh map

I have the following term, that should get minimized with Boolean algebra (no Karnaugh map!): (a ∧ ¬b ∧ c) ∨ (a ∧ c ∧ d) ∨ (b ∧ d) I already figured out, that the minimzed term is as follows (...
51 views

### Propositional logic meets diplomacy at the workplace

This is just a funny little incident that made me think. Please don't take it too seriously or the wrong way. I would still like to hear your opinion on it, though. I wrote an email to a colleague ...
30 views

94 views

### How can $P \lor Q,~ P \vdash \lnot Q$ be invalid?

While studying refutation tree and I came across this example: $P \lor Q,~ P \vdash \lnot Q$ in Outline of Logic- Schaum's series. The solution invalidates the argument. But, when we cross ...
30 views

### Distributive laws and Absorption laws with negation

I'm currently stumped because I can't seem to find a way though this proof I'm currently doing. I did notice because of this proof that I'm really not sure how to handle these two situations... 1) A ...
37 views

### Complementing function using DeMorgan's Laws

The question states find the complement of the following expression: x'y' + xy i am not sure about my solution which is: (x'+y') + xy
38 views

### Boolean expression simplification using 3 variables

(!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD) = (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(1) = (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(C + !C) = (!A B !C) + (B !C !D) + (!ACD) + (...
30 views

### Boolean expression simplification - Short problem

I don't know exactly how to simply this problem. I can clearly see that (A + B) is in all of them but I don't know what to do next. (A + B + C)(A + B + !C + D)(A + B + !C + !D) -- Edit 1 -- I am ...
47 views

58 views

148 views

### Need help formalising simple propositional logic sentences

I'm a beginner learning about propositional logic and how to formalise sentences. I'm currently working through the following sentences and translating them into logical statements. $p$ means “...
48 views

### Find the simplest proposition logically equivalent to $(p \Rightarrow q) \Rightarrow ( p \Leftrightarrow q)$

Here is what I've gotten so far ... $$(p\Rightarrow q) \Rightarrow ( p \Leftrightarrow q)$$ $$\Leftrightarrow (\lnot p \vee q) \Rightarrow ((p\Rightarrow q) \wedge (q\Rightarrow p))$$ \...
In what follows X is a set, A, B, C, etc., are subsets of X. The complement of a subset Y ⊂ X is denoted $Y^c$ . Prove the following implications, and for each draw Venn diagram. 1) A ⊆ B ⇒ A ⊆ (B ∪ ...