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)

2
votes
1answer
73 views

How to show $\vdash (\neg\neg p \rightarrow p)$.

Given these axioms: where $\phi, \psi, \theta$ are formulas $$ 1.:(\psi \rightarrow (\theta \rightarrow \psi))$$ $$ 2.: ((\neg \psi \rightarrow \neg \theta) \rightarrow (\theta \rightarrow \psi))$$ ...
0
votes
1answer
56 views

If no interpretations satisfy a set of formulae U, is it possible for $U\models A$?

Note: '$ \models$' denotes logical consequence, defined as If $U \models A$, then $A$ is a logical consequence of $U$, if and only if every interpretation that satisfies U also satisfies $A$, ...
-1
votes
2answers
103 views

Natural deduction: given premises, conclude $M \lor E$. [closed]

I need to prove that the following argument is valid using Natural Deduction: 1.  $[\lnot (B \lor \lnot I) \rightarrow (\lnot L \land J)]$ 2.  $[\lnot L \rightarrow (M \land B)]$ 3.  $\lnot (B \lor ...
0
votes
3answers
44 views

Proving logical consequence of a set

Prove or disprove the following: $(P \wedge Q), (\neg Q) \vDash (\neg P)$ I don't see how $\neg P$ could be a logical consequence of the set since it isn't similiar to any of the formulae within the ...
0
votes
1answer
36 views

Prove that $P \vDash X$ and $Q \vDash X$ implies $(P \vee Q) \vDash X$

Let $P \vDash X$ and $Q \vDash X$. Prove that $(P \vee Q) \vDash X$. This may seem to obvious but is there a formal way to prove this? couldn't I just state that $(P \vee Q) \vDash X$ is true since ...
0
votes
1answer
48 views

¬p ⊬ ⎕(p → q): Where's the mistake in my proof?

My professor noted on one of his slides that ¬p ⊬ ⎕(p → q). Intuitively, this seems correct; however, I can only prove that it is false. I suspect I've made a mistake in my proof. Where have I gone ...
0
votes
3answers
46 views

proving a logical consequence when subtracting a tautology from a set

IfI have a set X of Well-formed formulae and a Formula P. I know that X ⊨ P. If i am givin a tautology Q then prove that X - {Q} ⊨ P I don't understand why subtracting the set Q wouldn't make a ...
0
votes
1answer
18 views

rank propositional formula - exercise

Let $r$ be the rank function of a propositional formula, show that $r(\phi)<r(\psi)$ if $\phi$ is a proper subformula of $\psi$. I don't know how to prove it.
0
votes
1answer
55 views

transitivity of subformula relation - proof

Problem: prove that the relation "is a subformula of" is transitive for propositional formulas. let $\phi \in Sub(\psi)$ and $\psi \in Sub(\chi)$ prove that $\phi \in Sub(\chi)$. my proof: if $\phi ...
1
vote
2answers
67 views

Proof of induction principle

Theorem 1.1.3 (induction principle) of Dirk Van Dalen "Logic and Structure" states: Let $A$ be a property, then $A(\phi)$ holds for all $\phi \in PROP$ if: $A(p_i)$, for all i; $A(\phi),A(\psi) ...
0
votes
1answer
57 views

Need help finding a proof strategy for a propositional logic theorem

Textbook is Ben-Ari's Mathematical Logic for Computer Science. This question is taken directly from the homework that my professor assigned, not from the textbook. Definitions of interpretations and ...
9
votes
8answers
973 views

I can't understand logical implication

I just started studying logic (high school) anyway...for the truth table of logical implication If sentence $A$ is true and $B$ is true then $A\implies B$ is true. does that mean if $A$ and $B$ are ...
0
votes
2answers
33 views

Simplify $((p\wedge q) \vee (\neg p \wedge r) \vee (q \wedge r))$

$((p\wedge q) \vee (\neg p \wedge r) \vee (q \wedge r))$ $\iff$ $(p\wedge q) \vee r\wedge(\neg p\vee q)$ (Distributive Law) Not really sure where to go from here, need some hints please.
2
votes
2answers
128 views

How can the completeness of Hilbert's axioms be proven?

How can one prove that every propositional tautology, expressed with the connectives '$\neg$' and '$\rightarrow$', can be proved with the axioms below? (P0. $\phi \to \phi$) P1. $\phi \to \left( ...
0
votes
3answers
137 views

Can Hilbert (style) prove my tautology?

Can Hilbert (style) axioms prove the following tautology? $$A\wedge(C\rightarrow B)\oplus(A\wedge B\leftrightarrow C)\rightarrow(C\rightarrow(A\rightarrow B))\qquad\text{algebraic style} $$$$ ...
4
votes
4answers
114 views

$P \to Q \equiv \neg P \vee Q$

Most of the textbook that I had went through proves the given equivalence using truth table. But is there any way of proving $P \to Q \equiv \neg P \vee Q$ without truth table?
1
vote
1answer
247 views

A logic exercise (finite satisfiability)

I am new here and this is my first post. Had a logic exercise, thought of a solution but I am not sure. If the wff $(\phi_1 \wedge \phi_2 \wedge... \wedge \phi_n)\rightarrow \phi_0$ is valid and ...
2
votes
2answers
89 views

Deduction of a tautology

I am wondering what it means to "find a deduction for a tautology, say $((\neg(\neg A_0))\rightarrow A_0).$ I'm not really sure what a deduction is. Is it a sequence of formulas that satisfy the ...
1
vote
3answers
133 views

Prove that $2^{1/2}$ is irrational

I'm trying to understand each part of this completed proof that my professor did, here is my interpretation in parentheses, please advise as necessary. Proof: Assume that $2^{1/2}$ is rational, then ...
4
votes
1answer
57 views

Questions using If/Then and IFF

I'm having some trouble with statements of the form "if/then" vs "if and only if". Would someone mind giving me a sanity check here? My interpretation does not seem to make a lot of sense. Let ...
0
votes
2answers
124 views

Strengthening the Consequent: From A implies B, infer A implies (B ^ C).

Strengthening the Consequent: From A implies B, infer A implies (B ^ C). How do I construct a Fitch style proof to prove this?
1
vote
1answer
46 views

Translation of sentence to logic formula

Here are four sentences: If Jessy moves his truck, Irene will play her guitar Irene will only move her car, if Jessy moves his garbage cans It is not the case, that Jessy will move his ...
1
vote
1answer
33 views

Simplifying a Compound Statement

I have to simplify $\neg(s \wedge(t \vee u ) \wedge ((s \wedge t) \rightarrow u))$ I started by trying to using $(p \rightarrow q) \iff \neg p \vee q$ and DeMorgan's laws but things got messy. Any ...
2
votes
4answers
92 views

How to prove $C$ from $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$?

How does one prove $C$ from the premises: $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$ ? I've tried to prove $C$ by contradiction, using a sub-proof which presumes $\neg ...
0
votes
3answers
45 views

Simplifying a logical compound statement

I need to simplify $(p \vee r) \wedge (\neg p \vee \neg r)$ (if possible and using the laws of logic) I tried to substitue $s: (\neg p \vee r)$ but that made it even worse. Can anyone suggest an ...
2
votes
2answers
56 views

How would I go from DNF to a simplified formula with less symbols?

Here's a DNF: $$(\neg A_1 \land \neg A_2 \land \neg A_3 ) \lor (A_1 \land \neg A_2 \land \neg A_3 ) \lor (\neg A_1 \land \neg A_2 \land A_3 ) \lor (\neg A_1 \land A_2 \land \neg A_3 )$$ And the ...
2
votes
3answers
49 views

Why does adding material implication as an axiom to propositional calculus make every formula provable?

I've made it to section 12 in Kleene's Mathematical Logic, which is about completeness. Surprisingly, I was able to understand how every valid formula is provable. However, one of the exercises he ...
0
votes
0answers
28 views

First order logic, equivalence of queries to a database

My book says II should be equivalent to Select R.a,R.b from R,S where R.c=S.c I tried using this page http://en.wikipedia.org/wiki/First-order_logic I got this far. I understand II says for every ...
2
votes
1answer
23 views

Laws of equivalence

Need to proof using laws $$\lnot(p \land \lnot q) \lor q \equiv \lnot p \lor q$$ $\lnot(p \land \lnot q) \lor q$ $\equiv (\lnot p \lor \lnot(\lnot q)) \lor q\quad$ First De Morgan's law ...
0
votes
2answers
37 views

Truth table and the meaning of $\oplus$ in propositional logic

Could someone show me the truth table for this proposition? I think I have the last two down, but I'm not sure what the symbol in the following one is: $$p\oplus (p\wedge q)$$
1
vote
1answer
67 views

Natural deduction proof - I don't' understand the question

I am supposed to give a natural deduction proof of $$(P_1∨P_2), \neg P_1 ⊢ P_2$$ My assumption is $(P_1∨P_2)$ and I am going to derive $P_2$ from $\neg P_1$ or I am wrong? EDIT: Or I am going to ...
1
vote
1answer
90 views

How to prove that $P \rightarrow Q$ is equivalent with $\neg P \lor Q $?

In my book about Logic, which is called 'Language, Proof and Logic', by the way, there is explained that the conditional $ P \rightarrow Q $ is equivalent with $\neg P \lor Q$. There is another ...
1
vote
3answers
69 views

Deriving contradiction from $a\Leftrightarrow\neg a$

Recently I've been trying to prove some things by strictly following deduction rules. I've been trying to derive incononsistency from unrestricted comprehension axiom via Russell's paradox. I have ...
1
vote
2answers
35 views

$p ⇒ (q∨r) ≡ (p∧(\neg r)) ⇒ q$ are logical equivalent?

I have determine whether the following equivalence is true or not $$p ⇒ (q∨r) ≡ (p∧(\neg r)) ⇒ q$$ using logical equivalences definitions. I am never able to do these sorts of questions correctly no ...
1
vote
2answers
73 views

What does completeness mean in propositional logic?

During one of the lectures in logic, My prof proved completeness and soundness of Hilbert system of axioms or simple axiom system as in ...
0
votes
0answers
70 views

Proof of Propositional Compactness Theorem

I am going through the proof for the following form of compactness theorem. Statement: If Φ is an unsatisfiable set of propositional formulas, then some finite subset of Φ is unsatisfiable -- ...
2
votes
1answer
41 views

$\perp \Rightarrow p$ Syntactic Proof

Given the following axioms $$\begin{aligned}&1. p\Rightarrow (q\Rightarrow p)\\&2. [p\Rightarrow (q\Rightarrow r )] \Rightarrow [(p\Rightarrow q)\Rightarrow (p\Rightarrow r)]\\&3. \neg\neg ...
3
votes
3answers
129 views

Syntactically deduce $p\vdash \neg\neg p$

Given the following axioms $$\begin{aligned}&1. p\Rightarrow (q\Rightarrow p)\\&2. [p\Rightarrow (q\Rightarrow r )] \Rightarrow [(p\Rightarrow q)\Rightarrow (p\Rightarrow r)]\\&3. \neg\neg ...
1
vote
2answers
63 views

prove that a wff is not satisfiable.

for any pair of formulae p1 and p2, if both p1 -> p2 and p1 -> (not p2) are valid then p1 is not satisfiable. Prove by way of contradiction that this is true. My approach was assuming that p1 is ...
0
votes
2answers
65 views

Show that (p→q)→(r→s) and (p→r)→(q→s) are not logically equivalent.

This is a problem in my math book, however, the answer is in the back of the book as it is an odd. What I don't understand, is the fact that if I plugin r = T and p,q,s = F I end up with... ...
2
votes
4answers
101 views

Is proof by contradiction “same thing” as $A \rightarrow B$ is true when $A$ is false?

I encountered earlier today a question "Is the proof by contradiction same as that $A \rightarrow B$ is true when $A$ is false?" continued by "Are they related, then? How?" I think the answer is "no, ...
1
vote
5answers
83 views

Can the logic associative law be applied here?

$\big(p \rightarrow (q \rightarrow r)\big)$ is logically equivalent to $\big(q \rightarrow (p \rightarrow r)\big)$ I am a little confused when dealing with the 'implies' operator $\rightarrow$ and ...
5
votes
1answer
156 views

Equivalence between Peirce's law and Excluded Middle in Intuitionistic logic

I'm searching for a intuitionistically valid proof of the formula : $[((P→Q)→P)→P] ↔ (P \lor \lnot P)$ using the "standard" Hilbert-style axiom system from Kleene [1952], for ...
1
vote
1answer
73 views

Negation of a proposition of the form “not(p) & q”

This is a homework question I'm working on. I think it's right but I'm just curious if I'm supposed to state the negation of "but it is always right" differently. Find the negation of the ...
5
votes
1answer
213 views

If $x\rightarrow y$ and $y \rightarrow z$, prove, by contradiction, that $x \rightarrow z$

Say you're given $$x\Rightarrow y$$ $$y\Rightarrow z$$ Prove that $x\Rightarrow z$ by contradiction. It seems like such a simple task, because it's easy to evaluate that it must be true. But I ...
1
vote
1answer
64 views

Logical Notations for Mathematical Statements

I'm studying Discrete mathematics and I'm faced with a problem of converting a few descriptive mathematical statements into logical notation. Any help would be appreciated. Thank you. a). Any divisor ...
1
vote
3answers
55 views

Show that (P→Q) ∧ (Q→R) is equivalent to (P→R) ∧ [(P↔Q) ∨ (R↔Q)]

I literally have no idea how to start this proof. I get to (P→Q) ∧ (Q→R) = (¬P ∨ Q) ∧ (¬Q ∨ R) and then I get stuck.
1
vote
2answers
78 views

How can I use modus ponens or modus tollens to produce valid arguments? [closed]

I know this one is: $(1)$ If logic is easy, then I am a monkey’s uncle. I am not a monkey’s uncle. ∴ ? My answer: $\therefore$ Logic is not easy. (2) Can someone help me with this one? If ...
0
votes
2answers
70 views

Need help understanding valid arguments

I don't understand the following parapgraph in "Discrete Mathematics and Its Applications (Rosen)": "The argument form with premises p1, p2,...,pn and conclusion q is valid, when (p1 AND p2 AND ... ...
1
vote
0answers
28 views

Validity of Induction Proof - $\{ \land, \top, \bot \}$ is an incomplete set of connectives

I need to verify a proof of the fact that $\{ \land, \top, \bot \}$ is not complete. I consider $\top$ and $\bot$ to be $0$-ary logical connectives that are constantly true or false. That is ...