Stack Exchange Network

Stack Exchange network consists of 174 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).

-2
votes
0answers
15 views

Simplify the following expression. ¬[u ∨ (u ∧ r)] → ¬(r ∧ r)

so far I got: ¬[¬u ∨ (u ∧ r)] V ¬(r ∧ r)
1
vote
1answer
20 views

Show that the boolean formulas $[(p ∧ ¬q) ∨ q] ∧ [(¬q ∧ p) ∨ r] and (p ∧ ¬q) ∨ (r ∧ q)$ are equivalent.

So far I got this: $[(p ∧ ¬q) ∨ q] ∧ [(¬q ∧ p) ∨ r]$: $p∧ T ∧ [(¬q∧p) ∨ r]$ $p∧ [(p∧¬q) ∨ r]$ $p \lor r$ $(p ∧ ¬q) ∨ (r ∧ q):$ $(p ∧ ¬q) ∨ (q ∧ r)$ $(p ∧( ¬q ∨ q)∧ r$ $p ∧ T ∧ r$ $p ∧ r$
0
votes
1answer
26 views

Propositional logic - if, then, unless, consequence [on hold]

Need help to solve the below question. I need a direction so that I can apply the same to other questions. I understand what logical consequence means, and various propositional logics. EDIT1: ...
2
votes
1answer
56 views

What is the negation of $p\to \sim q$?

I know that the negation of $p\to q$ is ~p V q but I can’t seem to figure out the effect $\sim q$ will have on the negation. Also is their a way to check if something is the negation of a statement?
1
vote
0answers
38 views

Does this have a name? $\vDash(a_1\to(a_2\to(\cdots(a_{n-1}\to a_{n})\cdots)))\leftrightarrow((a_1\wedge a_2\wedge\cdots\wedge a_{n-1})\to a_n)$

For all formula $\alpha_1, \alpha_2, \cdots, \alpha_n$, $$\vDash (\alpha_1\to(\alpha_2\to(\cdots(\alpha_{n-1}\to\alpha_{n})\cdots))) \leftrightarrow ((\alpha_1\wedge \alpha_2\wedge\cdots\wedge\...
0
votes
0answers
11 views

From Xor to Milp formula

In the most part of the text books on Mixed Integer Linear programming, one can find that $P_1$ XOR $P_2$ XOR ... XOR $P_n$ can be transposed in $p_1 + p_2 + ... + p_n = 1$ where each $p_i$ is a ...
2
votes
2answers
50 views

How to use natural deduction to show $\neg (P \land Q) \vdash \neg P \lor \neg Q$?

How to use natural deduction to show $\lnot (P \land Q) \vdash \lnot P \lor \lnot Q$? I think I need to first assume $\neg(\neg P \lor \neg Q)$ and then find a contradiction but I cannot see how to do ...
1
vote
0answers
27 views

Equivalence of strings in modal logic

I'm trying to solve a question which asks me to show that for any two finite strings $O_1$ and $O_2$ of $\square$s and $\lozenge$s, (e.g. $\square\lozenge\lozenge\square\lozenge\square)$, that i) if $...
0
votes
0answers
17 views

Prove theorem in propositional calculus [on hold]

I want to prove that the following formula is a theorem in p1 here is the formula : ((P and Q) -> R) and (P -> Q)) -> (P -> R) Thanks :D
3
votes
1answer
40 views

Validity of $(\lozenge\phi\wedge\lozenge\psi) \rightarrow (\lozenge(\phi\wedge\lozenge\psi)\vee\lozenge(\psi\wedge\lozenge\phi))$ in modal logic

I'm trying to answer a question, one part of which asks me to provide either an informal semantic argument or a counterexample to determine whether $(\lozenge\phi\wedge\lozenge\psi) \rightarrow (\...
0
votes
2answers
32 views

Are the following logical statements all axioms of propositional calculus?

I have found conflicting lists of axioms in propositional calculus in Kleene, $2002$, and on Wikipedia. From what I can tell, carefully reasoning through each of the statements reveals that are ...
1
vote
2answers
63 views

How Does $AB{\sim} C + {\sim}ABC + {\sim} A {\sim}B{\sim} C$ Turn into $(A+C+{\sim}B)(B+{\sim}A)(B+{\sim} C)({\sim} A+{\sim} C)$?

I'm trying to figure out this Boolean algebra question and I cannot for the life of me figure it out. I know that the answer is $(A+C+{\sim} B)(B+{\sim}A)(B+{\sim} C)({\sim} A+ {\sim} C)$ but I can't ...
1
vote
2answers
80 views

Is it true that $((p\land q \rightarrow r) \land \lnot(p \rightarrow r)) \rightarrow (q \rightarrow r)$?

Is this a sound inference rule? $$((p \land q) \rightarrow r) \land \lnot(p \rightarrow r)) \rightarrow (q \rightarrow r)$$ So far I've rewritten it to $$((p \rightarrow r) \land \lnot(p \...
0
votes
2answers
42 views

Natural deduction (Logic) proof help

I'm very new to natural deduction and have been stuck trying to prove this argument all day: $A\to ¬B,$ $¬B\to ¬C,$ Therefore, $C\to ¬A$. I've been told I need to use modus tollens on the first ...
0
votes
1answer
51 views

If F satisfiable then ¬F is unsatisfiable.

If F satisfiable then ¬F is unsatisfiable. I know this is false and to show this I need to show a contradiction, this is my attempted answer, any ideas where I'm going wrong, this is revision for an ...
-1
votes
0answers
32 views

Sorites Paradox and Kleene's three-valued logic

I'm trying to solve an exercise in my logic textbook which asks me to suppose $P_n$ formalises '$n$-year olds are young', and consider a Sorites argument $$P_0, P_0\rightarrow P_1, ...,P_{99}\...
0
votes
1answer
44 views

Elementary Number Theory Divisibility Question

Let $a, b, c \in \mathbb Z$. I know that if $c|a$ and $c|b$, then $c|a \pm b$. I was working on some elementary number theory and I began to wonder if the following were true:$$\text{if }c|a \text{ ...
6
votes
3answers
83 views

Propositional calculus and intuitionist logic

Having never had much exposure to formal mathematical logic, I have decided to embark on a quest to rectify this; unfortunately having been exposed to concepts from Intuitionistic Logic through my ...
1
vote
4answers
44 views

Help with logical equivalence/proving not a contradiction

The question is this: Demonstrate using logical equivalences that $(p → q) ∧ (p → ¬q)$ is not a contradiction. Identify all logical equivalences by name. So far, I have $(p → q) \land (p → ¬q)$ a....
1
vote
0answers
27 views

Confusion about logical equivalence of particular sentences

Suppose a friend of mine is eating one of three distinct dishes, say $d_1, d_2,d_3$. Is the statement "I can see which dish my friend is eating" logically equivalent to "either I can see that my ...
0
votes
2answers
23 views

Can these propositions be equivalent?

We all know that: $P \rightarrow Q $ and $(Not)Q \rightarrow (Not)P$ are equivalent. Is it possible that in specific cases $P \rightarrow Q $ is equivalent with $Q \rightarrow P $ or $(Not)Q \...
1
vote
1answer
29 views

logic contradiction

Im learning about predicate logic from this textbook and I stumbled upon something that really confused me (both in phrase and in the contradiction I think I found). On page 64 there is a sentence "...
1
vote
2answers
47 views

Contrapositive of $p\land q \implies r$

Now I understand that strictly speaking the contrapositive of this statement would be $\neg r \implies \neg p\lor\neg q$, but what I would like to do instead is prove that $\neg r\land q \implies \neg ...
1
vote
2answers
33 views

Prove $p ↔ q$ and $(p ∧ q) ∨ (¬p ∧ ¬q)$ are equivalent using logic laws

I know that we can show this using a truth table but I can't prove it using logic laws. p ↔ q ≡ (p→q)∧(q→p) p ↔ q ≡ (¬p∨q)∧(¬q∨p) p ↔ q ≡ ¬p∨(p∧q) ∧ ¬q∨(q∧p) I go this far and then I'm ...
0
votes
1answer
21 views

Transform several disjunctions to implications

I want to transform a statement which only consists of disjunctions to a statement which only consists of implications. My statement: j => (a | b | c | d) Goal: new statement with only implications ...
2
votes
0answers
45 views

Show that the proof rule is not sound and proof question

I'm asked to show that the proof rule \begin{equation} \dfrac{\varphi \to \psi}{\lnot \varphi \to \lnot \psi} \end{equation} is not sound. To show this would I just make the truth tables for the ...
2
votes
4answers
42 views

Why $p \lor (\lnot p \land q)$ is not equal to $(p \lor \lnot p) \land q$ ? I had trying making Truth Table but, still can't figure it out?

Why $p \lor (\lnot p \land q)$ is not equal to $(p \lor \lnot p) \land q$ ? I had trying making Truth Table but, still can't figure it out ?
0
votes
0answers
88 views

Turn into Proposition logic

I am new to logic. I am suffering to turn one of the following sentences from normal form into propositional logic. Paragraph as follows: ...
0
votes
0answers
48 views

Proving that $a⊢b$ if and only if $a⇒b$ is a tautology

On my university exam paper there was a problem which description was the following: Prove the following assertion: $a⊢b$ if and only if $a⇒b$ is a tautology. How can I prove it?
-1
votes
0answers
29 views

what do we define definitely true?

I make the following statements p q r : p:if a pig has horns,then it can breathe fire. q:if a pig can breathe fire, then it has wings. r: if a pig has wings, then is has horns. Each statement is ...
0
votes
1answer
27 views

In the last statement, can i prove the contrapositive of it to be true to prove the statement?

I have worked out the problem A B C, my question is in the last statement " If the numbers e, π, π^2, e^2 and eπ are irrational, prove that at most one of the numbers π+e, π−e, π^2−e^2, π^2+e^2 is ...
2
votes
4answers
48 views

Natural deduction proof of $(A \to \lnot B \lor C), ((\lnot D \land A) \to B), (\lnot E \to A) \vdash D \lor (C \lor E)$

I'm struggling to proof this both if I use or introduction rule $\lor_{I_1}$ (to work on $D$) or or introduction rule $\lor_{I_2}$ (to work on $C \lor E$). Could you help me?
1
vote
1answer
81 views

As i got the contrapositive of this statement, how does e) necessarily follows from this? [closed]

An electronic circuit contains three light bulbs, X, Y and Z, which are each either on or off at any particular time. It is known that if bulb X is off or bulb Y is on, then bulb Z is on. Which one of ...
0
votes
3answers
55 views

In Discrete Mathematics, is there a difference between $(\neg P \wedge \neg Q)$ and $\neg (P \wedge Q)$?

I am wondering, in discrete mathematics, whether there is a difference between $(\neg P \wedge \neg Q)$ and $\neg (P \wedge Q)$. My query comes from a practice problem in a book: Either John and ...
-3
votes
1answer
107 views

Why do we even need first order logic?

I don't understand why propositional logic isn't enough. Can't any first order statement be encoded in the form of a propositional logic? What does first order logic do for us that we cannot do in ...
2
votes
4answers
70 views

Are True or False themselves propositions?

I’ve been arguing with my dad about whether or not True and False are actually propositions themselves, and I’d be curious to hear your thoughts. The definition of a proposition I’m seeing in most ...
1
vote
3answers
77 views

Trouble understanding proof to $\vdash ((\neg(\phi\rightarrow \psi))\rightarrow\phi)$?

I am having trouble understanding the natural deduction proof of $\vdash ((\neg(\phi\rightarrow \psi))\rightarrow\phi)$ (question 2.6.2 (b)) in Hodges and Chiswell's Mathemaical Logic. The natural ...
2
votes
1answer
101 views

Can any proof by contrapositive be rephrased into a proof by contradiction?

From my understanding, Proof by contrapositive: Prove $P \implies Q$, by proving that $\neg Q \implies \neg P$ since they are logically equivalent. Proof by contradiction: Prove $P \implies ...
1
vote
1answer
24 views

Propositional Logic: find sets $\emptyset \neq K_1 \subseteq K_2 \subseteq K_3 \subsetneq A$ such that $K_1, K_3$ are definable, and $K_2$ isn't

Edit: An assignment $v$ is a funcion $v : \{p_i : i \in \Bbb N\} \to \{true, false\}$ ($p_i$ are atomic variables). A set of Assignments $K$ is definable if there exists $\Gamma \subseteq WFF$ such ...
1
vote
1answer
35 views

Prove propositional formulas using Natural Deduction

(e) Show that $\vdash \lnot(p \lor \lnot p) \to p \land \lnot p$ (f) Show that $\models p \lor \lnot p$ and $\vdash p \lor \lnot p$. For the second part, you can assume (e), i.e. you can treat $\...
0
votes
1answer
38 views

$\models p \ \vee \ ( \lnot(q \ \wedge \ (r \rightarrow q)))$ is established or not?

I am learning propositional logic and I get a formula like this: $\models p \ \vee \ ( \lnot(q \ \wedge \ (r \rightarrow q)))$ I want to prove it is established or not by drawing a parse tree, but I ...
0
votes
0answers
41 views

Is this a Boolean algebra? (proof)

Let $B=\{0,1\}$ and the binary operations $\oplus,\cdot$ We define a bijection $\varphi$ s.t.: $$ \varphi:B \longrightarrow L=\{\mathbf{False},\mathbf{True}\}, $$ $$ \varphi(x):= \begin{cases} \...
0
votes
1answer
57 views

if $\vDash \alpha \ \Rightarrow \ \vDash \beta$ then $\vDash \alpha \to \beta$?

if $\vDash \alpha \ \Rightarrow \ \vDash \beta$ then $\vDash \alpha \to \beta$ ? Is this proposition true? And what about converse? I also wonder about the difference between $\Rightarrow$ and $\...
0
votes
1answer
21 views

Propositional Logic Translation

I am trying to convert the following into propositional logic in order to construct a semantic tableaux: If Mark goes to the party, then so does Pat. John or Pat will go to the party. John will not ...
0
votes
2answers
57 views

Why are these two simple statements equivalent?

As I study for my mathematical structures I final, I encountered a problem that I am unable to understand. The problem gives me the statement: If today is Tuesday, then we have class. I am being ...
5
votes
1answer
80 views

Partial truth values?

In his essay The Relativity of Wrong, Isaac Asimov famously wrote: When people thought the Earth was flat, they were wrong. When people thought the Earth was spherical, they were wrong. But if you ...
0
votes
4answers
54 views

Knights and knaves “I could say…”

I'm having trouble with classic knights and knaves problems that use the wording "I could say" or something similar. I haven't seen this variant discussed elsewhere, although versions of this problem ...
0
votes
2answers
59 views

Show $p \lor (p \land q ) \equiv p $ using equivalences

I am trying to show $p \lor (p \land q ) \equiv p $ using equivalences. I have tried many replacements (e.g. distributivity and de Morgans) but cannot see a way to simplify the left hand side that ...
0
votes
2answers
27 views

Propositional Logic - Deduction

So i have to prove that: $$\{\neg A\to B,A\to C,B\to D\}\vdash \neg C\to D$$ I can use logical axioms, modus ponens and 'metatheorems'. Logical axioms: φ→(ψ→φ) (φ→(ψ→χ))→((φ→ψ)→(φ→χ)) (¬φ→¬ψ)→(ψ→φ) ...
1
vote
1answer
37 views

$\Gamma_1 \cup \Gamma_2$ is not satisfiable iff there exists $\alpha \in WFF$ such that $\Gamma_1 \vdash \alpha$ and $\Gamma_2 \vdash \lnot \alpha$

Let $\Gamma_1,\Gamma_2 \subseteq WFF.\;$ Prove: $\Gamma_1 \cup \Gamma_2$ is not satisfiable if and only if there exists $\alpha \in WFF$ such that $\Gamma_1 \vdash_{HPC} \alpha$ and $\Gamma_2 \vdash_{...