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)

0
votes
0answers
24 views

A mathematical statement is logically equivalent to a related statement

I have to finish the statement: A mathematical statement and its ____________ are logically equivalent. My guess is contrapositive but I do not think that's right. Any help will be appreciated. ...
2
votes
3answers
28 views

How to show that if $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$

I'm new to boolean algebra and am having trouble proving the following simple theorem. Many thanks for any help. If $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$. ...
2
votes
1answer
69 views

Problem with proving formally tautology using given rules

Using the rules below prove that the following assumeptions leads to the following conclusion by tautology. $A\vee B \vee C, A\to C, B\to C \Rightarrow C$ What I did: $A\vee B \vee ...
0
votes
1answer
26 views

Is the True clause considered the proof of resolution refutation

So, basically I have the sentence $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P \Rightarrow R))$$ and it was asked to prove it by resolution refutation. On the ...
0
votes
0answers
20 views

Logic negate and simplify

Negate and Simplify: [(pvq)->~r]v~q Can someone show me step by step how to go about this. I am a little confused about negating over an implication.
1
vote
1answer
28 views

Conversion to CNF - eliminate implications

On the web I found a solution to an exercise on resoulution. Basically, it asks to use resolution refutation to prove $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P ...
0
votes
1answer
43 views

Propositional calculus logic question

In my assignment I have the following question: For every proposition $\theta$ let $E(\theta)$ be the set of basic propositions. Prove the following: For every two propositions, $\alpha$ and ...
5
votes
1answer
46 views

Compactness Theorem / Set made of formulas of infinite size

Could someone give me an example of an infinite countable set, where formulas contained in it are under the form of a conjunction or disjunction of infinite size, for which the compactness theorem ...
0
votes
1answer
24 views

How can I translate it into Logic sentence? [on hold]

Let $p$ denote "it is snowing." So how can I translate the following into symbolic logic? "It is not snowing, but snowing." Please help me.
2
votes
1answer
53 views

Structural Induction, Propostitonal formulae problem

I am kind of overwhelmed by this question. Can anyone give me some hints about where to start? Propositional formulae PF are inductively defined over the Boolean constants B := {1, 0} (true and ...
1
vote
2answers
41 views

Prove the two logic expressions are equal

Prove $\neg(a \lor b)$ is the same as $(\neg a \land \neg b)$ It makes sense when I think about it, but how does one prove it? Also is there a relationship with the above and saying: $(a \implies ...
2
votes
2answers
55 views

Every element of the empty set has three toes true or false? [duplicate]

This is a bonus question that we have and I cannot figure it out. Any help would be great! Is the proposition Every element of the empty set has three toes true or false? Explain your answer
1
vote
0answers
27 views

In a formal language, how does one show that $\neg \neg \bot \neq( \phi \wedge \psi) $ [duplicate]

In a formal language, how does one show that $\neg \neg \bot \neq( \phi \wedge \psi) $ Or how do one go about showing that the former is not a proposition. I've just started reading Dalen's Logic and ...
1
vote
2answers
38 views

Prove that it is a tautology

Let $P$, $Q_1$, $Q_2$ be some well-formed propositional formulas. Show that if $P\vee Q_1$ and $\neg P\vee Q_2$ are tautologies then $Q1\vee Q2$ is a tautology.
0
votes
3answers
34 views

Question about negating implied propositions

I'm negating this proposition: "If you study you will not fail." I'm using proposition P: "You study" and proposition Q: "You will fail." The original statement can be written as "$P → ¬Q.$" My ...
1
vote
4answers
70 views

Basic logic question: Can $\neg p \implies p$ be true?

Can $\neg p \implies p$ be true? How about $p \implies \neg p$? I was told yes, but it doesn't make sense to me. Any help would be appreciated!
0
votes
1answer
32 views

Given $p \rightarrow q$ and p are true, show $q ∨ r$ is true using rules of inference

I have a question from computing mathematics which I am not really able to prove. Given that $p \rightarrow q$ and $p$ are true, show that $q \lor r$ is true using rules of inference. Any ...
1
vote
2answers
66 views

Proof of a theorem in Hilbert's system

I have been trying to prove that the propositional formula $ \big( \alpha \rightarrow \lnot \beta \big) \rightarrow \big((\alpha \rightarrow \beta) \rightarrow \lnot \alpha \big)$ is a theorem in ...
1
vote
4answers
70 views

Need Hints Prove “$((\neg \alpha \to \alpha) \to \alpha) $” Using Axiom 1,2,3 and MP and deduction theorem

$((\neg \alpha \to \alpha) \to \alpha) $ Hi, I am trying to prove this. Can someone gives me some hints to start the question... My friend told me I might need to use deduction theorem here, but I ...
1
vote
1answer
16 views

Proposotional logic derivation

Show that (φ ∧ ψ) ↔ ¬(φ → ¬ψ) is derivable. I have derived ¬(φ → ¬ψ) from (φ ∧ ψ) by assuming (φ → ¬ψ) and (φ ∧ ψ) and deducing a contradiction. By cancellation of the hypotheses I can then conclude ...
0
votes
1answer
15 views

Conjuctive normal form of $(p\wedge(q\implies r))\implies s$

I am asked to write this in CNF without using truth tables. This is what I worked out so far: $$(p\wedge(q\implies r))\implies s \\ \neg(p\wedge (q\implies r)) \vee s\\ (\neg p \vee \neg(\neg q \vee ...
1
vote
1answer
34 views

Prove that simple conditional statement is tautology

This should be pretty easy, but I don't know how to turn the conditional statement into a tauntology. The statement is: $$ (p \land q) \to p$$ I am able to turn it into: $$ (\lnot p \lor ...
0
votes
4answers
67 views

Solve this proof using tautologies (no truth tables)

I am having trouble solving this problem using tautologies (no truth tables). Hypotheses: $t \rightarrow s,\;\; d \rightarrow (u \vee t)$ Conclusion: $d \rightarrow ( u \vee s)$
1
vote
1answer
38 views

Show that the function is an isomorphism between two $L$-structure.

The function: $$f: \mathbb{R} \longrightarrow (-1, 1)$$ $$ x \rightarrow \frac{x}{1 + |x|}$$ is an isomorphism between $\langle\mathbb{R}, <, =\rangle $ and $\langle(-1, 1), <, =\rangle$ where ...
0
votes
1answer
43 views

Logical Consequences and Ordered Fields.

How do I show that these two: $1.$ $\forall x(0 < x \rightarrow (-x) < 0)$ $2.$ $\forall x \forall y \forall z((x<y \wedge z<0) \rightarrow (y *z) <(x*z))$ are logical consequences ...
1
vote
1answer
36 views

Conversion from English Language to Logic Symbols

I have a problem in an example of Discrete Mathematics which my teacher worked in his lecture. He gave an argument and proved it that his argument was not valid, but the validity of argument is not ...
1
vote
1answer
93 views

Is infinite boolean algebra atomless?

I got two questions: 1) Does there exist an infinite Boolean algebra which contains an atom? I answered yes. 2) Does there exist an infinite Boolean algebra B such that for every b contained in B ...
1
vote
1answer
23 views

Prove that if $T$ is maximal consistent theory then $T$ is satisfiable

I want to prove that If $T$ be a maximal consistent subset of the set of all formulas then $T$ is satisfiable. By using the following facts I have proved for a maximal consistent $T$; ...
1
vote
1answer
118 views

Finding the atoms and elements of a Lindenbaum–Tarski algebra

Let B be the Lindenbaum–Tarski algebra with three variables $p,q,r$ (1) Find all the atoms of $B$. (2) How many elements of does $B$ have? So I think I know what an atom is, but I'm still not sure ...
0
votes
1answer
34 views

Modus ponens proof

I'm trying to prove that $\neg\bullet\varphi$ in system $L(\neg, \to, \bullet)$, $\bullet \varphi \approx (\varphi \to \varphi)$ Axiomas are the followind: A1) $\neg\neg\bullet\bullet\varphi$ A2) ...
0
votes
1answer
20 views

How to decide if propositional function is complete

I have two 3-ary propositional functions given by the table $$ \begin{array}{|c|c|c|c|c|} v(a) & v(b) & v(c) & v(f(a, b, c)) & v(g(a, b, c)) \\ \hline 0 & 0 & 0 & 1 & ...
-1
votes
1answer
49 views

To prove that an argument is valid with the rules of inference of propositional logic

Use propositional logic to prove that the following argument valid : $$(A→ ¬B) ∧ [D ∨ ¬ (C ∧ ¬B)] ∧ C → (A→D)$$
0
votes
1answer
14 views

Predicate formula to propositional formula

I have: $$\begin{align} \exists x \forall y P(x,y) \\ \end{align}$$ where $$\begin{align} M=\{a,b\} \\ \end{align}$$ I need to convert this formula to propositional logic. I know that if ...
0
votes
1answer
51 views

proof that p implies q entails not p or q [duplicate]

I could easily prove $\neg P \lor Q$ entails $P \rightarrow Q$. It is well known that $P \rightarrow Q$ entails $\neg P \lor Q$ but I couldn't find a way to prove it. Although there is the ...
0
votes
1answer
47 views

Modus ponens proof in system L(¬,→,∙)

I'm trying to prove $\neg\neg\bullet\varphi$ in system $L(\neg, \to, \bullet)$, where $\bullet$ is constant truth, i.e. $\bullet \varphi \approx (\varphi \to \varphi)$ Using modus ponens with ...
2
votes
1answer
20 views

Three atomic forms expression both in disjunctive and in conjunctive form?

we know that A v B is in both conjunctive and in disjunctive normal form. we also know that A ^ B is in both conjunctive and in disjunctive normal form. Does it follow from this, that A v B v C is ...
1
vote
1answer
40 views

Don't really understand the absorption law

I don't really get the absorption law, specifically in this case: $$ (\lnot p \lor q) \land (\lnot r \lor q) \equiv (\lnot p \land \lnot r) \lor (\lnot p \land q) \lor (q\land \lnot r) \lor (q \land ...
0
votes
3answers
33 views

Logical Expression : Is it same or not?

I have $p\rightarrow \left ( q\wedge r \right )$, If i negate it: It will become like below: $\lnot \left ( p\rightarrow \left ( q\wedge r \right ) \right )$ $\lnot \left ( \lnot p\vee \left ( ...
1
vote
1answer
29 views

What is the conjunctive normal form of the boolean constant TRUE?

I have the following problem: Is TRUE (or 1) a logically equivalent formel in conjuctive normal form to a tautology? How can I build the conjunctive normal form ...
1
vote
1answer
29 views

using the elimination rule in natural deduction

Prove that $$(A ∧ B) \to C ⊢ A \to (B \to C)$$ Am I using the conjuction elimination rule correctly? Or am I assuming too much? $(A ∧ B) \to C$ (Given) $A \to C , B -> C$ (∧E 1) $A ...
2
votes
4answers
58 views

Prove $Q \rightarrow \neg(Q \rightarrow \neg P)$

I have an exercise about proving statements: Suppose that P is true. Prove that Q → ¬(Q → ¬P ) is true Givens: $P$ $Q \rightarrow \neg P$ Goal: $\neg Q$ which I simply prove ...
3
votes
1answer
25 views

Show functionally completeness property for propositional logic

Let $n>0, n\in \mathbb{Z}$ and let t,f denote true and false. For every function $$g:\{t,f \}^n \to \{t,f\} $$ There is a propositional forumala $B$, using only the connectives ...
2
votes
3answers
68 views

How to show that something is not logically entailed?

I was just thinking about entailment and would like to know if you can show that something is NOT entailed by the premises. I know that to show $A, A → B \vdash B$, I could just provide a proof ...
4
votes
4answers
62 views

semantics(truth) vs formal system?

my first question is can we just define semantics in logic and not define a formal system ? why do we need a formal system to prove a proposition when for example we know the proposition is true ? ...
2
votes
2answers
32 views

The existence of conjunctive/disjunctive normal forms?

I am studying propositional logic/calculus and I am currently learning about normal forms. The algorithm to construct a conjunctive/disjunctive normal form from any given formula is straightforward. I ...
0
votes
1answer
27 views

natural deduction on proving a claim

I am working on this proof and wanted to know if I am using the ID natural deduction rule correctly. Can I just assume B and A based on that rule? ...
3
votes
0answers
104 views

Propositions logic and problem solving

How can a question of this nature be approached: Two avid game players Alice and Bob play three different games. They are very competitive and so would do anything within the rules of the game to ...
1
vote
1answer
38 views

Translate the following argument into propositional logic, and then assess it for validity.

This is question 9 from exercise 6.5.1 in Smith and Cusbert's Logic: The Drill. It wants a translation and test of validity for the following: Catch Billy a fish, and you will feed him for a ...
0
votes
0answers
36 views

Prove that the truth value of $x_1 \lor x_2 \lor \ldots \lor x_n$ does not depend on how the formula is parenthesized

So the question is: Generalized Associativity of $\lor$. Prove that, for all positive integers $n$, all ways of parenthesizing the following logical statement have the same truth value: $$x_1 \lor ...
2
votes
2answers
52 views

Prove $\lnot \lnot B$

Prove: $\lnot \lnot B$ from $\lnot \lnot A \implies \lnot \lnot B, \lnot(A \implies B) $ I cant use excluded middle: $B \lor \lnot B$ So I choose $\lnot B$ as hypothesis and will try to get $B$ ...