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
60 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
112 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
49 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
63 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
119 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
33 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
47 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 ...
0
votes
1answer
51 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
504 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
64 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
41 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
46 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
47 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
47 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
65 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
34 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
76 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
93 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
156 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 ...
1
vote
1answer
55 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
3
votes
3answers
88 views

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true … can I argue that?

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true ... can I argue that? I don't see how I can argue that $(A \vee C)$ must be true because can't we have $(T \vee T) ...
2
votes
3answers
66 views

Indirect proof , odd and even numbers

"Show by indirect proof that if 5n + 3 is an even number then n is an odd number" How could this be solved? I guess I'm in the right track but I don't know how to conclude.
3
votes
2answers
54 views

How to prove the following using direct proof

$[(\sim p \vee q) \wedge p ] \Rightarrow q $ What should be done next in order to apply direct proof to the example above? The following process has been already done but seemingly it's incorrect: ...
0
votes
1answer
45 views

Conversion of disjunctive normal form to conjunctive normal form

Explain how $ (p \lor q \lor r \lor s) $ can be re-written into an equivalent CNF formula such that each clause contains exactly $3$ variables or negations of variables.
0
votes
2answers
98 views

Understanding logical form of “Nobody in the calculus class is smarter than everybody in the discrete math class”

I'm self studying How to Prove book and have been working out the following problem in which I have to analyze it to logical form: Nobody in the calculus class ...
0
votes
1answer
35 views

Analyzing Logical Forms involving quantifiers

I have been solving the following problem from How to Prove book: Analyze the logical forms of the following statement: Everyone likes Mary, except Mary ...
0
votes
1answer
43 views

Readings on more general/abstract notions of induction related to logic

Can someone suggest references to understand the more general/abstract concept of induction? Specifically, I am trying to justify to myself what is called induction on the "complexity of a ...
1
vote
2answers
58 views

Validity in propositional calculus.

I have read some of the answers on similar questions but I can't really get my head around this. So, here are 2 questions I need to answer. Show using a truth table: That the inference ...
1
vote
1answer
65 views

Thinking logically instead of Venn diagrams

I hit upon the following identity while reading the book How to Prove: $$(A \cup B) \backslash B \subseteq A$$ Now if I solve this logically I can reduce this like this: $$ \begin{gather*} x \in (A ...
-3
votes
2answers
55 views

What is the Equivalent formula of $((a\to b) \to ((a \to c) \to (c \to a)))$ [on hold]

Need help to solving a logic. The question is to find an equivalent to the following logic. $((a\to b) \to ((a \to c) \to (c \to a)))$ Thanks in advance for help.
-3
votes
3answers
55 views

Find an equivalent to $(p\lor q) \to (p \lor r)$ [on hold]

I need some help regarding solving a logic. The question is to find an equivalent to the following logic. $(p\lor q) \to (p \lor r)$ Thanks in advance for help.
3
votes
1answer
43 views

Why is the assumption needed in this conditional introduction?

In the first derivation detailed here, why must we include a subderivation with $P$ as an assumption? We can derive $Q$ (4) from $S \land Q$ (2) without the help of $P$ (3); and then since we have ...
6
votes
1answer
218 views

Unique decomposition of wffs when left and right parentheses are indistinguishable

I'm working through Enderton's book A Mathematical Introduction to Logic 2nd Edition for self study. Section 1.3 Exercise 7 Suppose that left and right parentheses are indistinguishable. Thus, ...
0
votes
1answer
22 views

Is my interpretation of these propositional formulas correct?

We define two propositions P and Q as follows. P: Victoria studies hard for the final exam. Q: Victoria desperately wants to ace the final exam. (a) Translate each of the following statements into ...
2
votes
1answer
63 views

Simplifying ambiguous statements

I have been working on the following question from Velleman's How to prove book: Let S stand for the statement “Steve is happy” and G for “George is happy.” What English sentences are ...
3
votes
2answers
43 views

Forming up Complex logical forms from simple one

This is another problem I have been working from Velleman's How to prove book. Let P stand for the statement “I will buy the pants” and S for the statement “I will buy the shirt.” What English ...
0
votes
3answers
63 views

Logical form of Either and Neither: Alice in room

This is one of the problem I have been working: ...
1
vote
2answers
43 views

Method of verifying answers

I have been reading Velleman's How to prove it book and solving problems of the exercise in it. What concerns me is that I cannot verify if actually my solutions are correct. The book has only ...
4
votes
11answers
572 views

Propositional logic problem about a conversation of four people who lie or tell the truth

This is obviously elementary but can't figure it out. I am taking a course named Logic and Introduction to Analysis next semester and wanted to do some reading beforehand but to figure out how deep ...
2
votes
1answer
37 views

Does introduction and elimination rule for an operator determine uniquely its truth table?

My question is regarding the inference of a truth table for an operator given how it behaves according to introduction and elimination. This follows from an exercise I read, and it got me thinking if ...
1
vote
1answer
55 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
2
votes
1answer
48 views

Relation between an unsatisfiable set and a tautology

In mathematical logic, satisfiability and validity are elementary concepts of semantics. A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true. A ...
1
vote
2answers
45 views

Reducing $ab' + cb + ac$ to $ab' + cb$

Boolean expressions $I = ab' + cb + ac$ and $J = ab' + cb$ have the same truth table. Then why expression $I$ can't be reduced to expression $J$?
1
vote
1answer
81 views

How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
4
votes
1answer
173 views

How to prove Post's Theorem by induction?

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...