Tagged Questions

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
2answers
35 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
44 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
22 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
18 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
32 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
49 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
63 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
60 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
32 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
53 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
49 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
36 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
109 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
48 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
45 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
95 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
66 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 ...
-2
votes
2answers
44 views

How to find a Boolean expression for a combinational logic circuit?

How to find the logic expression for a logic circuit? For example, this one. I am unsure what the circles before the gates exactly mean.
4
votes
1answer
104 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
68 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
211 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
54 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
49 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
61 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
65 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
23 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 ...
2
votes
2answers
58 views

Proving that $(\neg p \vee q)\wedge (p\wedge (p\wedge q))\iff (p\wedge q)$

Having trouble with this question: If $p,q$ are primitive statements, prove that $$(\neg p \vee q)\wedge (p\wedge (p\wedge q))\iff (p\wedge q)$$ Source: Discrete and Combinatorial Mathematics ...
0
votes
3answers
72 views

(Homework) Prove the law of syllogism

Trying to prove, by symbol manipulation, that if $(P \rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R)$ I am stuck after doing these steps: (P $\rightarrow Q) \wedge (Q ...
4
votes
1answer
26 views

Going from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨~q)

I am confused on how to go from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨ ~q). I know they are equal because I plugged them into a truth table and all of the rows have the same values. What would be some ...
2
votes
1answer
46 views

Propositional Calculus : Showing $\{ \lnot, \# \}$ is not complete

Let the ternary connective $ \# $ stand for the majority connective. Accordingly, the truth value of $ (\# p q r) $ is $T$ if a majority of $p, q, r$ are true. $(\#pqr)$ is false if a majority of ...
0
votes
3answers
62 views

Equivalence of $P\rightarrow Q$ and $\lnot P\lor Q$

How do we explain the logical equivalence $$(P\rightarrow Q ) \equiv [(\neg P)\; \vee \; Q]$$ and if possible could you please give an example illustrating this equivalence. Thanks alot !!
0
votes
1answer
24 views

Is there a simplifying algorith m for a formula in Disjunctive Normal Form?

Apologies if this question has been asked before. Please point me to it. I could not find it. Given a propositional formula which is Disjunctive Normal Form, is there an algorithm which outputs ...
2
votes
2answers
51 views

Is this truth table correct?

Is this truth table correct? Sorry for the formatting Truth table for $p ∧ c$ and $p ∨ c$, with $c$ representing a contradiction: $$\begin{array}{cc|cc} p & c & p∧c&p∨c \\ \hline T ...
1
vote
2answers
74 views

Subproof in Fitch style system

When using a Fitch style system for proving various theorems, why are we allowed to assume anything we want in the assumption of a subproof in order to derive some desired result? It seems like there ...
1
vote
1answer
28 views

Are these statements negated correctly using De Morgan's laws?

$-10 < x < 2$. Negation: $-10 \geq x$ or $x \geq 2$. $x \leq -1 \text{ or } x > 1$ Negation: $-1 > x \leq 1$
1
vote
2answers
46 views

Diffucult Tautology to Prove

I'm trying to show that the following is a tautology: (p or q) and (not p or r) implies (q or r) Can anyone help, as far as I can get is to the following: [(not p and q) or (p and not r)] or ...
2
votes
1answer
46 views

Inference Challenge in First Order Logic [closed]

I ran into old exercise on FOL in Artificial Intellegence. any one could help me? Suppose we have $ E \bigwedge R \Rightarrow B$ $ E \Rightarrow R \bigvee P\bigvee L $ $ K \Rightarrow B$ $ \neg ...
1
vote
2answers
362 views

Definition of “contradiction” and use of the term for “⊥”

If one looks in Internet for definition of “contradiction” (including respective words in other languages), one finds a mess. See for example this index of Wikipedia articles in various languages. The ...
1
vote
2answers
62 views

Show that this argument is valid.

¬p → C; ∴ p. Where C denotes a contradiction. What does it mean by ¬p → C;? Also another statement ¬p → F; ∴ p. Is there any differences between the two statement since from my understanding a ...
0
votes
1answer
37 views

Determine whether the argument is valid or invalid

. Determine whether the following argument is valid: $$\displaylines{ 1:p\cr 2:p ∨ q\cr 3:q → (r → s)\cr 4:t → r\cr ∴ ¬s → ¬t.}$$ Suppose $$\displaylines{¬s → ¬t.}$$ is False, we have s=F; t=T To ...
0
votes
1answer
44 views

Determine whether the argument is valid or invalid

$$\displaylines{ ¬p → (r ∧ ¬s)\cr t → s\cr u → ¬p\cr ¬w\cr u ∨ w\cr ∴ t → w\cr}$$ I have the solution which shows We start by noticing that we have (How did we know we have to start here?) ...
1
vote
2answers
45 views

Is this a valid proof of $(A∧B’) ∧C↔(A∧C) ∧B’$?

So I am supposed to prove $(A∧B’) ∧C↔(A∧C) ∧B’$ using wffs and equivalence rules. I have never done such proof, and I want to check if my steps are correct. This assignment is only graded based off of ...
0
votes
1answer
41 views

Prove tautology without truth table

This has been asked before, but I have different problems. I’m asking because this was not discussed in class and I’m unsure of the procedure in obtaining the proof. The two in question are the ...
0
votes
0answers
42 views

Understanding why a disjunctive normal form is equivalent to the proposition

I'm having trouble understanding the equivalence relation bet. a proposition and its disjunctive normal form (DNF). For example, in the example on p.51 ...
2
votes
1answer
59 views

p implies q statement means that if p is true, q also has to be true

I don't understand this statement. Looking at the truth table, if p is false, the statement is always true. if p is true and q is true, the statement is true. if p is true and q is false, the ...
0
votes
2answers
33 views

Sorting out logic homework with a friend.

My friend and I were looking over my homework and he pointed out something that he thought was incorrect. I was to write sentances using logical connectives. The original sentance was: "To get ...
1
vote
1answer
71 views

Proving that a propositional theory of any cardinality has an independent set of axioms

This is exercise 1.2.19 from Chang & Keisler's Model Theory, which has been giving me a headache for some time now. Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. ...
0
votes
1answer
68 views

Propositional Logic Puzzle - Enderton

This is a question from Enderton. You are in a land inhabited by people who either always tell the truth or always tell falsehoods. You come to a fork in the road and you need to know which ...
2
votes
2answers
50 views

Proposition into spoken language

Given: $\sim( p \leftrightarrow (q \vee r) )$ $p:$ It's raining $q:$ The sun is shining $r:$ There are clouds in the sky. Translate the proposition into spoken language. ...
3
votes
5answers
149 views

Is $'' \sum_{n = 1}^{\infty} (-1)^n \; \text{is a real number}''$ an invalid statement or a false proposition?

So we're beginning an introductory logic course and my professor is giving examples for valid statements/ propositions - meaningful statements that are either true or false but not both. So he puts ...