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
313 views

p xor q xor r — simplifying into disjunctive normal form with propositional algebra

So, I have $p \oplus q \oplus r$, and my goal is to simplify into disjunctive normal form with propositional algebra. Step 1: simplyify xor ((($p \wedge \neg q) \vee (\neg p \wedge q)) \wedge \neg ...
1
vote
1answer
302 views

How to prove Lemma 2.12 of Mendelson without Deduction Theorem

My question refers to Bourbaki's axiom system in Nicolas Bourbaki, Théorie des ensembles (1970). [page I.25] : $(P \lor P) \supset P$ --- (Taut) $Q \supset (P \lor Q)$ --- (Add) $(P \lor Q) ...
0
votes
1answer
77 views

Using truth tables to determine logical equivalency

How do you use truth tables to determine whether or not the following pairs of statements are logically equivalent? i) (p ᴧ q)→r ii) p→(q→r) I'm confused on how you would do that, Thanks
2
votes
3answers
35 views

Put $(a \leftrightarrow b) \wedge c$ in DNF

$$(a \leftrightarrow b) \wedge c$$ I'm having problems with this. If I do: $$(a \rightarrow b) \wedge (b \rightarrow a) \wedge c$$ then $$(\neg a \vee b) \wedge (\neg b \vee a) \wedge c$$ But now I'm ...
1
vote
3answers
306 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: For any relations $R,S$ and $T$ of $\mathcal{T}$, the relations ...
1
vote
1answer
28 views

Is it possible to prove an argument is not satiable with equivalences?

I am trying to prove is this argument: (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) is satiable with equivalence. Is what I said below valid for this? (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) q ∨ (p ∧ ¬p) ...
0
votes
1answer
403 views

Propositional Logic with rules of inference problem.

$$ \begin{array}{l} 1.\>\>\>\> (r ∧ ¬s) ∨ (q ∧ ¬s)\\ 2.\>\>\>\> ¬s → ((p ∧ r) → u)\\ 3.\>\>\>\> u → (s ∧ ¬t)\\ ...
0
votes
1answer
68 views

Rules of Inference…From the following premises, conclude that p → q.

1. (r ∧ ¬s) ∨ (q ∧ ¬s) 2. ¬s → ((p ∧ r) → u) 3. u → (s ∧ ¬t) ----------------------- Prove from the previous arguments. p → q Hey guys, I am really lost, so far I ...
1
vote
1answer
58 views

Equivalence Proof (p ∧ q) ∨ ¬(p → q) ∨ ¬(q ∧ r).

I am trying to prove (p ∧ q) ∨ ¬(p → q) ∨ ¬(q ∧ r) ≡ ¬r ∨ (q → p). So far I have done the following: (p ∧ q) ∨ ¬(¬p ∨ q) ∨ ¬(q ∧ r) Implication Definition (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬q ∨ ¬r) De ...
1
vote
2answers
111 views

not p whenever q — do i understand this?

The phrase is not p whenever q. I take this to mean the same thing as not p if q. When p is false, q can be true or false. When p is true, q is false. When q is true, p is false. When q is false, p ...
1
vote
1answer
53 views

Name for DNF simplification rule / prime implicants under closure?

I was reading this question which links to this list of propositional equivalences. One of the equivalences shown (T5a) is: $$ A \wedge B \vee A \wedge \neg B \equiv A $$ I have used this rule by ...
0
votes
4answers
126 views

Proving a proposition is a tautology

I have to prove $P \lor ( Q$ XOR $R) \lor (R \rightarrow Q)$ is always true. I got $P \lor ( R \rightarrow \lnot Q ) \lor (R \rightarrow Q)$. Now I'm stuck at this part. I have no idea how to ...
0
votes
1answer
72 views

Propositional Calculus basic rules

I've been learning propositional calculus and proofs and I'm not sure if we are able to write $(P \lor Q) \leftrightarrow (\lnot P \rightarrow Q)$. If I am doing a proof will i be able to replace (P v ...
4
votes
3answers
170 views

A question about Implicational Propositional Calculus

My question is motivated by a previous post about Implicational calculus Having showed that Mendelson (A1) and (A2) axioms plus Peirce's law are a complete axiom set for implicational fragment of ...
2
votes
3answers
807 views

Deduction Theorem + Modus Ponens + What = Implicational Propositional Calculus?

Implicational propositional calculus is a system of propositional calculus in which implication is the only logical connective, and all other connectives are defined with respect implication and a ...
0
votes
2answers
55 views

If “If $A$, then $B$ and not $C$” is true, then is “If $A$ and $C$, then not $B$” true?

Suppose "If $A$, then $B$ and not $C$" is true. Is the following statement true? If $A$ and $C$, then not $B$. I know the answer is true but I don't know the basis behind it.
2
votes
1answer
80 views

How to solve Distributivity of $\lor$ over $\land$

The problem I need to prove is $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ I am trying to get the RHS equivalent to the LHS So I change $(p \lor q) \land (p \lor r)$ (using the Golden ...
0
votes
2answers
77 views

Curry-Howard isomorphism for disjunction elimination

I am trying to find out how the disjunction elimination rule of natural deduction relates to the Curry-Howard isomorphism. The rule: $P \vee Q, P \Rightarrow C, Q \Rightarrow C \vdash C$ I have been ...
1
vote
2answers
106 views

Circuit Logic NAND

I have to build a circuit using only NAND gates. But I wasn't given an equation. Instead I was given this formula: F(wxyz)= E m(0,1,2,3,4,5,7,14,15) Function of (wxyz) = Sum m(0,1,2,3,4,5,7,14,15) ...
0
votes
1answer
81 views

Confusion in Conjunctive normal forms

Which of the Following is TRUE about formulae in Conjunctive Normal form? For any formula, there is a truth assignment for which at least half the clauses evaluate true. For any formula, there is a ...
1
vote
2answers
77 views

How is this disjunctive form found through propositional algebra

I'm learning about disjunctive normal form and the algebra of propositions. The text is Discrete Mathematics with Graph Theory, 3rd Edition by Goodaire and Parmenter (it wasn't highly recommended on ...
4
votes
1answer
118 views

How to derive this equivalence in propositional logic

This is a homework assignment from a discrete math class that I never took - it asks how to prove the statement $\neg \neg p \equiv p$. The catch is that only the following equivalences can be used: ...
1
vote
1answer
38 views

Logical Proposition simplification

I'm Trying to simplify this: $$ [(¬p \vee ¬q)\to¬(r \vee s)] \wedge ¬s \wedge r$$ so far, I got into this: $$ [(p \wedge q) \vee (¬r \wedge ¬s)] \wedge r \wedge ¬s$$
0
votes
2answers
40 views

Logical Equivalence with →

I am given the problem of proving: $p → (q\land r) \equiv (p→q) \land(p→r)$ Using known logical equivalences. I'm not well practiced in transforming logical statements that contain →'s in them into ...
0
votes
2answers
396 views

Propositional Logic, P or Q but not both.

If I had two propositions, P and Q, and wanted to write an expression such that either P or Q are true but not both, what would be the best notation for it?
1
vote
6answers
179 views

Logic - Is $A \rightarrow ( B \rightarrow C) $ equivalent to $A \rightarrow C$?

I know that $A \rightarrow B$ and $B \rightarrow C$ resolves to $A \rightarrow C$ but does $A \rightarrow (B \rightarrow C)$ also resolve to $A \rightarrow C$?
1
vote
3answers
43 views

How to read parens

How do you read the parentheses in this proposition? That is, what do you say in English when reading from the end of a parenthesis to the next? Are the parens simply read as "such that"? $ ( ∀ x ∈ Z ...
1
vote
6answers
360 views

Determine if tautology, contingency or contradiction

I have to determine if the statement is a tautology, contradiction or contingency. Been at it for days but didn't get too far. The original question is $$\left((\lnot p\vee z)\wedge(p\vee ...
0
votes
2answers
40 views

Intro to Discrete Structures $\;\lnot A \rightarrow (A \rightarrow B)$

Im trying to use propositional logic to break this down but i have no clue. i know about the rule that if a wff ends in form ....implies (a implies b), the a can be ...
0
votes
2answers
66 views

$(A \lor B) \land C \iff (A \lor C) \land (B \lor C)$?

Assume $A$, $B$, and $C$ are three independent predicates. Maybe $A$ stands for "my age is 20," and $B$ "stands for tomorrow is a good day." So is it true that $(A \lor B) \land C \iff (A \lor C) ...
0
votes
1answer
29 views

Using the resolution method in logic

Using the resolution method in logic, having these clauses $$\{ \neg M \vee S, \neg S \vee T, \neg W \vee T, W \vee M, \neg T, \neg T \vee S \}$$ is it possible to reach the contradiction directly ...
1
vote
2answers
145 views

How can I show that three statements are not logically equivalent to another?

I am given three premises and a conclusion. The premises are: \begin{gather} p \lor q \\ p \to \mathord{\sim}q \\ p \to r \end{gather} and the conclusion is $$ r $$ I used a truth table and showed ...
-2
votes
1answer
155 views

Propositional Logic use of simplification?

Can I use Simplification when it's not the only logical connective in a proof? For example: $(P \wedge Q) \Longrightarrow C$ premise $P \Longrightarrow C$ Simp. 1 $ Q \Longrightarrow ...
0
votes
4answers
116 views

Symmetric difference equality

Something I was thinking about earlier: If $A\triangle B=A \triangle C$, does $B=C$? Where $\triangle$ is symmetric difference. My intuition is telling me no, but I can't seem to think of an example ...
1
vote
2answers
156 views

First-order logic: how-to produce interpretation where a given formula is false?

For example, given Theory T with predicates $$A(x), B(x), C(x,y), D(x,y), x=y$$ axioms $$\exists x.A(x) \land \exists x.B(x) \land \exists xy.C(x,y)\\ \forall x(A(x) \leftrightarrow \neg B(x)),$$ ...
3
votes
6answers
139 views

Show that $\neg(p \Longleftrightarrow q)$ and $p \Longleftrightarrow \neg q$ are logically equivalent

Given there are 2 logical variables $p$, $q$ . Show that $\neg(p \Longleftrightarrow q)$ and $p \Longleftrightarrow \neg q$ are logically equivalent without using the truth table. And here is my ...
1
vote
0answers
303 views

Propisitional logic exam questions and answers

I'm going over exam questions, since my exam is hours away. I'd be extremely grateful if you could check out my answers and evaluate them. Hopefully you guys can see the truth table. Also, i have ...
2
votes
0answers
57 views

Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
2
votes
1answer
93 views

Are my answers for these propositional calculus questions right?

Formalize the following English sentences as propositional logic formulas: $i)\quad$ "When the front and back doors are closed then the light is off." $ii)\quad$ "Either the lift doors are open or ...
0
votes
2answers
93 views

Where do the brackets go in $p \wedge q \vee \neg p \rightarrow \neg q$?

I have been give the following question for homework: Let $p$ be the statement "She will graduate" and let $q$ be "She will find a job". Then what would be: "Either she will graduate and find ...
1
vote
0answers
109 views

Propositional logic truth tables

For the exam that I am taking, propositional always comes up with identical questions. These include writing a sentences in propositional logic, which I can do. But also drawing a truth table for ...
4
votes
5answers
168 views

Are $p \to (q \to r)$ and $p \to (q \wedge r)$ logically equivalent?

Is $p \to (q \to r)$ logically equivalent to $p \to (q \wedge r)$? I simplified each one, I got $\neg\, p \vee(q \vee r)$ and $\neg\, p ∨(\neg\, q \wedge r)$ respectively. Not sure if my ...
1
vote
1answer
63 views

Does $\neg(x > y)$ imply that $y \geq x$?

Given any arbitrary binary relation $\geq$ defined on some set $S$, we define a new binary relation $>$ on $S$ by: $$ x > y \quad\text{iff}\quad (x \geq y) \wedge \neg(y \geq x) $$ In accordance ...
2
votes
1answer
303 views

How to check the validity of this argument using the rules of inference?

I have this argument : I play basketball and football. If today isn't Saturday, then I play basketball and football. If today is Friday OR today is Saturday, then I don't play football. Therefore, ...
6
votes
2answers
332 views

Is this a valid proposition?

Consider following two sentences. $x^2 = 1.$ Today is Thursday. The first statement can't be a proposition. because the truth of (1) depends on the value of $x$. For some values of $x$ it is true ...
1
vote
1answer
52 views

Mathematical logic question propsitional logic

"When the front and back door are closed then the light is off" p - "front" q - "light is off" r - "back doors are closed" $$(p\land r) \rightarrow q$$ Would this be logically correct?
2
votes
4answers
1k views

Satisfiability Problem: Determining Which People To Invite

When planning a party you want to know whom to invite. Among the people you would like to invite are three touchy friends. You know that if Jasmine attends, she will become unhappy if Samir is ...
2
votes
3answers
100 views

Truth table logic

Can someone please show me how this works, i'm going out of my mind I know the truth tables for the individual AND, OR AND NOT but when it comes to them being combined my understanding is shattered ...
0
votes
3answers
84 views

Inferential logic in a simple-life situation.

Here's a little situation I want math to resolve for me : If I study, I make the exam , If I do not play tennis, I study , I didn't make the exam Can I conclude that was playing tennis ? Trying ...
6
votes
7answers
431 views

Conditional Statements: “only if”

For some reason, be it some bad habit or something else, I can not understand why the statement "p only if q" would translate into p implies q. For instance, I have the statement "Samir will attend ...