# Tagged Questions

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 ...
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 ...
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 ...
73 views

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 ... 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)$... 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 ... 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 ... 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 ... 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 ) ...
59 views

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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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)}$ ...
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 ...
89 views

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 ...
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. ...
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 ...
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 ...
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 ...
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 ...