Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

1
vote
1answer
65 views

What do the first two say?

Three children walk into the kitchen, Mom asks each one in turn "Does everybody want juice?". The third child says "yes" , what does the first two say? My thinking: ...
0
votes
0answers
22 views

Relations and quantifiers

When talking about relations, we know that the relation is anti-symmetric if "for all x: for all y: R(x,y) AND R(y,x) IMPLIES (x=y)". But can i rewrite this as "for all x: for all y: R(x,y) EXCLUSIVE ...
1
vote
2answers
85 views

Proof about Clavius's Law

Clavius's Law claimed: $(\neg A \rightarrow A) \rightarrow A$ What it is the proof about it in Deductive System $L$? Deductive System $L$ is: L1: $A \rightarrow (B \rightarrow A)$ ...
0
votes
2answers
94 views

Show that $(p \to q)\land(q \to r)\to (p \to r)$ is a tautology. [closed]

Show that $(p \to q)\land(q \to r)\to (p \to r)$ is a tautology. How to prove this without using truth table? I think it need some existing tautologies like $p\to q\iff \neg p\lor q, \:\: p\land ...
0
votes
3answers
56 views

How to represent a logic equivalence?

In propositional logic we have the DeMorgan's laws: $$\lnot (p\lor q) \Leftrightarrow \lnot p\land \lnot q$$ $$\lnot (p\land q) \Leftrightarrow \lnot p\lor \lnot q$$ I would like to teach the ...
0
votes
2answers
50 views

$(A \lor B) \to C$ and $(A \to C) \lor (B \to C)$ one entails the other?

For a homework assignment I have to prove that one of the statements entails the other. The statements are: $(A \lor B) \to C$ $(A \to C) \lor (B \to C)$ the only thing that I got so far is either ...
1
vote
1answer
52 views

Proof for sequent (Logic) [closed]

I'm currently trying to prove the following: http://i.imgur.com/dACOdOS.png And this is what I've come up with so far: http://i.imgur.com/mC69m5l.png And now I'm stuck. Perhaps the next step might ...
0
votes
1answer
44 views

Equivalence Rule for Sequent Calculus

Why are there no inference rules for equivalence (≡ on the right and ≡ on the left) for the sequent calculus, and if there was, how would they look like? e.g. (1) $\cfrac{?}{\Gamma,(A \supset B) ≡ ...
0
votes
1answer
38 views

Disjunctive normal form to conjunctive and vice-versa

Is there a way i can go from dnf to cnf quickly? Can I simply negate dnf to get cnf? and get negate cnf to get dnf? e.g. $P \to (Q\wedge \neg (P \to R))$ = $\neg P \vee (Q \wedge \neg ( \neg P \vee ...
0
votes
1answer
42 views

CNF formula induction proof

I am trying to prove the following theorem: Every proposition formula is logically equivalent to a formula in CNF. As a hint, they say that this can by proven by an induction on the structure of the ...
3
votes
3answers
59 views

Proving $\{\neg(r\to p)\lor[(\neg q\to\neg p)\land(r\to q)]\}\to(\neg p\lor q)$ is a tautology without a truth table

Hello! I'm having problems trying to figure out this. Here is what I did: I used implication relation and Demorgan's law to simplify this proposition. I then used associative and commutative laws ...
2
votes
2answers
34 views

On the alleged circularity of the definition of implication and double implication

Note: I'll use the convention adopted by my professor: "$\rightarrow$" is the symbol for implication and "$\implies$" for deduction. Our professor defined implication as The connective such that ...
1
vote
1answer
37 views

Show Logic Equivalence

$(A \wedge (B \vee C) \implies (A \wedge C) = \neg A \vee \neg B \vee C$ Attempt: $\neg(A \wedge (B \vee C)) \vee A \wedge C$, by $(x \implies y) \equiv (\neg x \vee y)$ $\neg A \vee \neg(B \vee C) ...
0
votes
1answer
69 views

Show there's no RAA-free derivation of $(P_1\to P_2)\lor (P_2\to P_1)$

Show there's no RAA-free derivation of $(P_1\to P_2)\lor (P_2\to P_1)$. (Hint: Look for a normal such derivation.) Solution: Here are the theorems we have learnt from the normal deduction chapter. ...
0
votes
1answer
45 views

Logic - Propositional calculus

I don't understand how to show the following: (!Q -> P) ∧ !P -> Q I understand the answer is true as I did it with a truth table but how can I prove this using propositional logic? Thanks!
0
votes
2answers
65 views

Explanation and example of a deduction method

I need to find the deduction from the set $\{\neg S \lor R,R \rightarrow P,S\}$ such that the last component is $P$. The textbook gives the long rigorous definition of deduction but no examples to ...
0
votes
1answer
35 views

If $Γ,A \vDash B$ and $Γ,A \vDash \lnot B$, then $Γ \vDash \lnot A$

The task is to show that for every set Γ of propositions: If $Γ,A \vDash B$ and $Γ,A \vDash \lnot B$, then $Γ \vDash \lnot A$. This follows Gallier's notation and is actually taken right out of his ...
0
votes
1answer
38 views

Proving tautology by substitution

How do I prove whether the following statement is a tautology or not using substitution? ∃x,P(x)∧∃x,Q(x)⇒∃x,(P(x)∧Q(x)) From what I understood if the expression is of the form A⇒A, then we can ...
0
votes
2answers
32 views

Validity of Well formed Fromulas

How to prove whether this well formed formula is a tautology or not? ∃x,P(x)∧∃x,Q(x)⇒∃x,(P(x)∧Q(x)) So far my approach has been assuming P(x) to be a statement with a truth value(say,"x is odd") and ...
1
vote
2answers
127 views

Catalogue of propositional logic laws

I have searched for it in Wikipedia and this site and I haven't found it yet. What I have found isn't complete enough -maybe a short list of ten or so equivalence laws, perhaps forgetting all together ...
0
votes
1answer
35 views

deduction for propositonal logic [duplicate]

given problem is, If $\Sigma\vdash\varphi$ iff $\Sigma\vdash\psi$, then $\Sigma\vdash\varphi\leftrightarrow\psi$. I can prove this using sound&completeness theorem but I don't know how to do ...
0
votes
1answer
44 views

Using the distributive law in propositional calculus

So I was given this proof in class: ~p ^ q = (~ p v q) ^ ~(~q ^ p) = (~ p v q) ^ (q v ~p) by double negative law. = ~p ^ (q ^ ~p) v ( q ^ ( q ^ ~p)) by distributive law. ...
5
votes
3answers
162 views

Proving $[(p\leftrightarrow q)\land(q\leftrightarrow r)]\to(p\leftrightarrow r)$ is a tautology without a truth table

I came across the following problem in a book: Show that if $p, q$, and $r$ are compound propositions such that $p$ and $q$ are logically equivalent and $q$ and $r$ are logically equivalent, then ...
-1
votes
1answer
47 views

proving logic without using truth table

Without using truth table, show that the conjunction of $(1) \; q \cdot (r \vee s\cdot t) \supset u$ and $u \vee r \supset p$ implies (2) $q \supset p \vee s$ we allows "u" count as sentence letter ...
1
vote
1answer
22 views

Need help with propositional logic [Proof]

I need help with proving $\neg a \vee b$ is logically equivalent to $$ \neg (((a \vee b) \wedge \neg (a \wedge b)) \wedge (a \vee ~b)) $$ by using logical equivalence law. I have tried multiple times ...
4
votes
3answers
109 views

How can we prove $(P \to \neg P) \to \neg P$ in this system?

It's been days that I'm stuck in a simple proof of $(P \to \neg P) \to \neg P$ using an axiomatic system, and, whenever I think I'm closer to it, I just found I'm walking in circles. The system goes ...
1
vote
1answer
20 views

Having trouble translating sentences into propositional logic

Translate the following sentences above into propositional logic, using the scheme below. B = Bones is a hothead K = Kirk is a hothead S = Spock is a hothead U = Uhuru is a hothead Neither Uhuru ...
2
votes
2answers
42 views

Propositional Logic: How to reason about the “empty” list?

Suppose $n=0$, how do this definition make sense in that case ? In this case the book states that this list of formulas $\Phi_i$ evalute to $\top$ for all valuations. But what reasoning can I use to ...
0
votes
1answer
31 views

Propositional Logic: Validity of sequent $\lnot\Phi_1 \land \lnot \Phi_2 \vdash \Phi_1 \rightarrow \Phi_2$

Propositional Logic: Validity of sequent $\lnot\Phi_1 \land \lnot \Phi_2 \vdash \Phi_1 \rightarrow \Phi_2$ $\lnot \Phi_1 \land \lnot \Phi_2$ (premise) $\Phi_1$ (assumption) $\lnot \Phi_1$ ...
1
vote
1answer
52 views

Fitch-style proof propositional logic

I am usually quite good with these but i just can't wrap my head around this once for some reason. I have to make a Fitch-style proof for the expression: $(s \rightarrow p) \lor (t \rightarrow q) ...
0
votes
1answer
17 views

Proposition Translation

For this, I got (not p and not s)---> not T. Here is my thinking. The word unless is giving me a hard time so I used an anolgy and made a random sentence. "Open the door unless you are sick" = " ...
1
vote
0answers
9 views

Truth of propositional formula (dependence on variable)

Identify the correct statements about $2^n\ge100$. The choices are: This is a proposition This is not a proposition Its truth value depends on the value of $n$ Its truth value ...
0
votes
1answer
43 views

Normal Deduction

I am going through normal deduction and I am pretty confused right now. I have read the definition: Definition: A derivation (in propositional logic) is normal if no main premise in an elimination ...
0
votes
1answer
33 views

Checking if a statement is a Taututology

I have this question As per http://web.stanford.edu/class/cs103/tools/truth-table-tool/ This statment is not a tautuology.So is the question wrong?
1
vote
1answer
55 views

How to show that there is a deduction of $\varphi\leftrightarrow\psi$

Problem is showing or disproving in Sentential logic that: If $\Sigma$$\vdash$$\varphi$ iff $\Sigma$$\vdash$$\psi$, then $\Sigma$$\vdash$$\varphi\leftrightarrow\psi$ But I wonder how to show that ...
1
vote
1answer
37 views

Converting to disjunctive normal form?

The formula is: ¬((p → ¬q)∨(r∧¬s)) and what I've done so far is this : ¬((¬p∨¬q)∨(r∧¬s)) ¬(¬p∨¬q)∧¬(r∧¬s) (p∧q)∧(¬r∨s) After this step I became really confused as to how to proceed. I'm not sure ...
0
votes
1answer
111 views

Checking Validity of Arguments using Rules of Inference

Im trying to understand how a theorem or statement is proved using Rules of Inference.I have this example I really don't understand how they say.Now p->q may be true with p being false.Then ...
0
votes
0answers
32 views

intuitionistic logic and propositional logic equation

Show that for propositional logic: $\vdash_i \neg \phi \Leftrightarrow \vdash_c \neg \phi$. How can I solve this?
2
votes
2answers
56 views

Clarification needed regarding DeMorgan's Law

I'm currently going through Daniel Velleman's "How to Prove It". He states DeMorgan's Law as follows: 1. $\neg (P\wedge Q)$ is equivalent to $\neg P \vee \neg Q$ 2. $\neg (P \vee Q)$ is ...
2
votes
1answer
60 views

How to convert to disjunctive normal form?

The formula is: $\lnot((s \lor \lnot p) \land (q \land r))$ and what I've done so far is this: $\lnot(s\lor\lnot p) \lor\lnot(q\land r) $ $(\lnot s\land p) \lor (\lnot q\lor\lnot r)$ After this ...
0
votes
1answer
65 views

Natural Deduction - use RAA

Give natural deduction proofs showing each of the following: a) $\phi\vdash\top$ for any formula $\phi$. b) $(P_1\to P_2)\vdash (\lnot P_2\to\lnot P_1)$. c) $(\lnot P_2\to\lnot P_1)\vdash (P_1\to ...
2
votes
1answer
38 views

Is my working or 'logic' correct?

Question is if I am able to create a DNF from ¬(¬pɅ(pVq)) to exactly like this : (¬pɅq) V (¬pɅ¬q) ? I have tried for a long time and here is what I worked out which I'm not able to find out if I am ...
1
vote
1answer
40 views

Proving that $[(A \to X) ~\text{or}~(B \to Y)] \to [({A ~ \text{and} ~B}) \to (X ~ \text{or} ~Y)]$ without a truth table

I am tasked with proving the following: $$[(A \to X) ~\text{or}~(B \to Y)] \to [({A ~ \text{and} ~B}) \to (X ~ \text{or} ~Y)].$$ Can anyone tell me what this statement is: Valid, Satisfiable or ...
0
votes
2answers
29 views

Formalized attempt of proof that well ordered-ness ( of subsets of $\mathbb{Z}$ that are bounded below) implies induction seems to have issue?

I want to prove that well-orderedness on the integers implies induction. The proof is the classical "assume a contradiction" and see what happens. So begin with an intended contradiction: ...
1
vote
3answers
89 views

Natural deduction - Logic and Proof

Given the premise P ∨ ¬ Q by natural deduction prove (P → Q) → ((¬ P → Q) → Q) I am trying to prove this using a Case Proof in Fitch For my initial subproof, would I be correct in assuming P ∨ Q. ...
1
vote
3answers
45 views

Proving that $\neg((P\vee Q)\to R) \iff (P\wedge \neg R)\vee(Q\wedge\neg R)$ without a truth table

Prove, using propositional calculus, that $\neg((P\vee Q)\to R) \iff (P\wedge \neg R)\vee(Q\wedge\neg R)$. My work: $$(\neg (P\vee Q) \vee\neg R) \\ ((\neg P\wedge \neg Q) \vee\neg R) \\ ...
0
votes
2answers
27 views

Solution set of a linear system with three equations and three unknowns with at least two distinct solutions.

Proposition: If $(x_0, y_0, z_0)$ and $(x_1, y_1, z_1)$ are two distinct solutions of a linear system with three equations and three unknowns then $t(x_1-x_0, y_1-y_0, z_1-z_0)$ is also a ...
-1
votes
2answers
57 views

Testing validity of Predicate Logic conditional statement without a Truth Tree.

For the past half hour, I have been trying to prove the following statement in Predicate Logic without the use of a truth tree: $$∃xPx∧∃xQx→∃x(Px∧Qx)$$ Which, of course, I know to be invalid. As ...
3
votes
1answer
65 views

Natural deduction: Derive $(\phi\lor\psi)\lor\sigma\to\phi\lor(\psi\lor\sigma)$

Exercise: Derive $(\phi\lor\psi)\lor\sigma\to\phi\lor(\psi\lor\sigma)$ It's pretty hard for me to understand what I'm supposed to do. It was kinda easy to solve the first few exercises from my ...
0
votes
1answer
33 views

Show that $A\subseteq B$ if and only if for any set $C$, one has $(A\cup C)\subseteq (B\cup C)$

Show that $A\subseteq B$ if and only if for any set $C$, one has $(A\cup C)\subseteq (B\cup C)$ $\exists x\in A\cup C \land \exists x\in B\cup C$ $(\exists x\in A\lor \exists x\in C) \land (\exists ...