1
vote
1answer
54 views

Using the compactness theorem

I am working through problems which ask you to apply the compactness theorem (from propositional logic) to problems. How would you go about solving this one? Let $\mathbf{L}$ be an arbitrary ...
1
vote
1answer
31 views

It is false that if p then q.

I'm doing some homework in which I'm converting textual descriptions of logic statements to their respective symbolic representation. If one reads ...
0
votes
1answer
35 views

How's my proof?

Prove that not every boolean function is equal to a boolean function constructed by only using $∧$ and $∨$. If p,q = (0,1) (p$∧$q)$∨$q = (0$∧$1)$∨$1 = 1 (p$∧$q)$∨$~q = (0$∧$1)$∨$~1 = 0 Therefore ...
3
votes
1answer
73 views

Prove if Tautology, Contradicton, or Neither. Is my proof ok?

Determine whether $((p \Rightarrow q) \Rightarrow r) \Leftrightarrow (p \Rightarrow (q \Rightarrow r))$ is a tautology, a contradiction, or neither. If $p,q,r = (0,0,0)$ then $((p \Rightarrow ...
1
vote
1answer
49 views

Proof by induction of propositional formulas

I have two inductively defined operations: $\text{bin}$ base case: If $p$ is a propositional letter, then $\text{bin}(p) = 0$ inductive step $\text{bin}(\neg \phi) = \text{bin} (\phi)$ ...
0
votes
1answer
81 views

Can you conclude that A = B if A, B, and C are sets such that…

a. A ∪ C = B ∪ C b. A ∩ C = B ∩ C c. A ∩ C = B ∩ C and A ∪ C = B ∪ C My method of solving this was to convert everything to propositional logic, then to solve it to show that none of the above are ...
1
vote
1answer
94 views

Answering questions with truth tables

"With every dinner I have three rules": If I don't drink wine, then I eat soup If I eat soup and drink wine, then I'll have some pudding If I have pudding or don't drink wine, then I'll skip the ...
2
votes
1answer
46 views

formal proof - logic

I am trying to prove the following, using natural deduction: $$p\wedge q\Leftrightarrow p \vdash p \Rightarrow q$$ with the following but i seem to get stuck. I know i have to prove $q$, but am not ...
0
votes
1answer
108 views

Propositional calculus proof must involve instance of $(\neg \neg p \Rightarrow p )$

Hi this is a question about propositional calculus. The axioms I am working with are: $(p \Rightarrow (q\Rightarrow p))$ $ ((p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q ) ...
-3
votes
1answer
59 views

Boolean algebra help please!

Let $a, b$ be any elements in a Boolean algebra. Prove that the following statements are equivalent: a) $a = ab$ b) $ab^{'}=0$ c) $a^{'}+ b = 1 $ [Hint: Show the following chain of implications: ...
1
vote
5answers
104 views

Verify that $\bigl(p\to(q\to r)\bigr)\to \bigl((p\to q)\to (p\to r)\bigr)$ is a tautology.

Verify that $\bigl(p\to(q\to r)\bigr)\to \bigl((p\to q)\to (p\to r)\bigr)$ is a tautology. I am confused on this whole tautology even after looking at examples both in my book and on-line. I ...
1
vote
1answer
48 views

Prove or refute: $A_1,\ldots,A_n\vdash_{CPL} B \iff (A_1 \wedge \ldots \wedge A_n)\vdash_{CPL} B$

Need to prove or refute: $A_1, \ldots, A_n \vdash_{\rm CPL} B \iff A_1 \land\dots\land A_n \vdash_{\rm CPL} B$ Since we have $\iff$ operator, we have to deal with to directions. Let's begin from ...
2
votes
2answers
66 views

Prove or refute contingent: If A implies B is contingent, then B is too

The question is: If $A, A \to B$ are contingent, then so is $B$ $A, A \to B$ (implies) is a contingent, but how exactly to show «so is $B$»? If I'm using a truth table, how should I show that ...
2
votes
0answers
57 views

Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism ...
4
votes
3answers
146 views

Natural deduction proof of $(\alpha\to\beta)\to(\beta\to\gamma)\to(\alpha\to\gamma)$

My teacher has assigned us this exercise as part of our homework: Give a natural deduction proof of $(\alpha\to\beta)\to(\beta\to\gamma)\to(\alpha\to\gamma)$ Here is an example of natural ...
1
vote
0answers
32 views

Deriving ¬R from {R↔(R∨(P∧¬P)),R↔¬P,¬P→(P↔(Q→Q)),P→Q} [duplicate]

Give a derivation of $\neg R$ from the following premises: $$\{R\leftrightarrow(R\lor(P\land \neg P)), R\leftrightarrow\neg P, \neg P\to(P\leftrightarrow(Q\to Q)), P\to Q\}$$ using the ...
0
votes
0answers
14 views

predicate calculus and using the Euclidean algorithm [duplicate]

So I have this problem which I can't seem to prove. Define the predicate RP(a,b) for positive naturals a and b as follows. RP(a,b) is defined to be true if and only if one of the following is true: ...
1
vote
2answers
125 views

Solving logic word problems

So I have a number of statements of this "murder" word problem that I must solve. I will try and simplify them as much as possible. So I have these 4 different facts: If Sarah was drunk then either ...
1
vote
2answers
78 views

Relations in Propositional Logic

It is my understanding that relations are best described with predicate logic. I have a homework question that asks me to convert English sentences into propositional logic. The following list of ...
0
votes
1answer
30 views

Clarification about negation in propositional logic

I am a little stumped on the concept of resolution, and want to clarify that something is correct, primarily negation. if an expression in CNF is ${x = (a \lor b) \land (\lnot a \lor \lnot b)}$ ...
1
vote
1answer
148 views

Truth Trees, Propositional Logic where conclusion is not related to premises

I have a problem that involves an argument in Propositional Logic. However, the conclusion has nothing to do with the premises (completely different variables). I'm fairly certain that this makes the ...
-1
votes
1answer
89 views

boolean expression help simplify

Question 1 $$\begin{align*}A'BC + AB'C + ABC + A'B'C' &=A'B C + B' C (A +A') + ABC\\ &=A'B + C + B'C + ABC \end{align*}$$ Question 2 $$\begin{align*}A'B + B'C + CB &=A'B + C(B +B')\\ ...
1
vote
1answer
42 views

Translating propositional formulas

I've been given statements to translate into a propositional formula. The question states that it may also be possible for a statement to have multiple interpretations. I've having trouble ...
1
vote
1answer
78 views

Proof through induction that all formulas with a certain characteristic are a tautology or logical equivalence of p

First, sorry for the long title but I couldn't figure out how to summarize it better. This is a homework question for my course "Introduction to Logic" and I can't figure out how to solve it. The ...
3
votes
1answer
755 views

Translating sentences into propositional logic formulas.

I have some trouble with translating certain sentences into a statement of propositional logic. It is homework, so I will also be happy with some hints. Please keep in mind that I translated these ...
0
votes
1answer
882 views

A Proof relating to the Disjunctive normal form

Here is a problem from Kenneth Rosen's Discrete Mathematics and its Applications, Section 1.3 Suppose that a truth table in $n$ propositional variables is specified. Show that a compound ...
2
votes
3answers
123 views

Proving $(A \land B) \to C$ and $A \to (B \to C)$ are equivalent

Prove that $(A \land B) \rightarrow C$ is equivalent to $A \rightarrow (B \rightarrow C)$ in two ways: by semantics and syntax. Can somebody give hints or answer to solve it?
2
votes
2answers
1k views

Every sentence in propositional logic can be written in Conjunctive Normal Form

While reading through Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following question: Any propositional logic sentence is logically equivalent to ...
2
votes
3answers
225 views

Use rules of inference to show

Premises: $p \land \lnot s$ $q \to (r \to s)$ Conclusion: $(p \to q) \to \lnot r$ Use rules of inference to show the above argument is valid. I only manage to get $(p \to q) \to (p \land ...
1
vote
2answers
97 views

Need help with solving proposition logic formula, should be a tautology

I have the following formula: $(((p \vee q) \rightarrow r) \wedge (p \rightarrow q))\rightarrow (q\rightarrow r)$ The truth table for this formula shows that this is a tautology. However, I get ...
2
votes
2answers
307 views

Rewriting Conditionals In Their Well Known Form

The question is, "Write each of these statements in the form “if p, then q” in English. [Hint:Refer to the list of common ways to express conditional statements.] a) It snows whenever the wind ...
2
votes
3answers
270 views

Writing Propositions With Propositional Variables

The puzzle I am working on is: "Let $p$, $q$, and $r$ be the propositions $p$: Grizzly bears have been seen in the area. $q$: Hiking is safe on the trail. $r$: Berries are ripe along the trail. ...
2
votes
1answer
204 views

Transcribing Propositions In English To The Language Of Logic

The question I am working on is: Let $p$ and$q$ be the propositions $p$:It is below freezing. $q$:It is snowing. Write these propositions using $p$ and $q$ and logical connectives (including ...
1
vote
1answer
285 views

Determine Consistency Of System Specifications

I am looking at an example problem in my text: "Determine whether these system specifications are consistent: 'The diagnostic message is stored in the buffer or it is re-transmitted.' 'The ...
4
votes
3answers
193 views

Negating “Zach blocks e-mails and texts from Jennifer”

I am reviewing some basic propositional logic. The question that I have come across that has given some confusion is Zach blocks e-mails and texts from Jennifer where I am asked to find the negation ...
1
vote
1answer
322 views

Evaluating Logical Statements

The problem I am working on is, "Analyze the logical forms of the following statements: (a) Alice and Bob are not both in the room. (b) Alice and Bob are both not in the room. (c) Either Alice or ...
3
votes
5answers
629 views

Tautology, Contradiction, or a satisfiable equation? Confusion about implication.

I'm having some trouble with a homework question. I have the following $ P \rightarrow \neg P$ This looks like a contradiction to me. This should never be true! Yet, if I transform it using $p ...
1
vote
1answer
104 views

Finding a resolvent for clauses

I have the following question and am not sure how to do it. Find the resolvent for the two clauses: $P \vee \neg Q \vee R$ $P \vee \neg R \vee S$
5
votes
7answers
296 views

How can I Prove that $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology?

Prove that $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology Laws of logic I tried prove it by using truth table but it didn't produce a tautology. This is my work so far: $$ [(p \to \neg ...
0
votes
1answer
38 views

How can I progress this derivation?

I'm learning propositional calculus in a discrete mathematics course. I'm trying to kick the habit of using axioms like equations and now I'm a little stuck and could use a nudge. Using a compact ...
2
votes
1answer
90 views

Does this proof using Novikov axiomatic propositional logic hold?

This question seems absolutely elementary but I'm having a hard time completing the proof, in fact I may have taken a bit of a left turn on it or I may be improperly applying axioms all together. ...
3
votes
2answers
726 views

Formation sequence for a logic formula

I will start with some definitions from An Introduction to Mathematical Logic and Type Theory: To Truth through Proof by Peter B. Andrews then give the exercise that I am working along with my attempt ...
2
votes
1answer
259 views

Multiple variables for a logical expression?

I wanted to know if what I did is even on the correct path for how this question is worded. How can you have two variables when it's dealing with a single unhappy person? I'm guessing the third way ...
2
votes
2answers
254 views

Written as disjuctions, conjunctions and negations?

With a domain from -2 to 2 I'm trying to write the following using disjunctions conjunctions and nagations. I'm not sure how correct I am and wanted to know if I did them correct? Could someone help ...
2
votes
1answer
154 views

Proving an implication by proving its dual

My textbook "Discrete and Combinatorial Mathematics, an Applied Introduction" by Ralph P. Grimaldi contains the following definition: Let $s$ be a statement. If $s$ contains no logical connectives ...
1
vote
1answer
199 views

Logic translation involving the existential quantifier and “such that”

A: "There exists an integer greater than 5 such that it is less than 10" B: "There exists an integer such that it is greater than 5 and less than 10." C: "There exists an integer less ...
0
votes
3answers
1k views

Express the propositional form ie. using only the NAND operator.

Recall that the NAND operator(denoted by "|") is equivalent to AND followed by negation; that is, for any two propositions a and b, the propositional form (a|b) is logically equivalent to ¬(a∧b). ...