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
0answers
28 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
39 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
35 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
71 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
33 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
89 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
78 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
18 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
16 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
40 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
87 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
41 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
50 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
46 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
127 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
33 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
148 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
36 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
57 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
15 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
62 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
23 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
43 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
35 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
33 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
31 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
59 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
26 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
73 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
5answers
75 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
41 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
30 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
117 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
44 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
38 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
54 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$ ...
3
votes
1answer
52 views

Why is a not-not-p invalid in a logical clause?

I have an assignment and it states that while $(p \vee q) \vee \lnot r$ is valid, $(p \vee q) \vee \lnot(\lnot r)$ is invalid in a logical clause, but I don't see why. A clause is described as being ...
0
votes
2answers
42 views

For any set of formulas in propositional logic, there is an equivalent and independent set

A set of formulas is independent if no proper subset is logically equivalent to it. Note that this exercise appears in Enderton 1.2 10(c) and is marked as star.
1
vote
1answer
34 views

Distribute ANDs over ORs in this sentence

Can someone explain how we turn the sentence $$[\neg C(x,y)]\vee [\neg A(x) \vee B(x)\wedge C(x,y)]$$ into conjunctive normal form by distributing the ANDs over the ORs? It's confusing me because ...
1
vote
3answers
47 views

Reverse of Deduction Theorem

Why is it "easy to see" that if $S \vdash (A\to B)$ then $S \cup\{A\} \vdash B$?
0
votes
1answer
53 views

Justify each step in the following proof of Proposition 3.9 (a). I like to know if I'm in the right track and I'm also missing a few of them

Proposition 3.9(a): If a ray r emanating from an exterior point of triangle ABC intersects side AB at a point between A and B, then r also intersects side AC or side BC. proof. (a) Let r= array XD ...
3
votes
1answer
50 views

FOL and Conjuctive Normal Form Conversion

I see the CNF from following firs order logic: $ \forall x [ \forall y [ \neg A(y) \vee B(x,y) \Rightarrow [ \neg \forall y B(y,x) ] ] $ is equivalent to : $ (A(f(x)) \vee \neg B(g(x),x)) \wedge ...
1
vote
1answer
26 views

propositional-calculus/logic riddle

Two physicists, A and B, and a logician C, are wearing hats, which they know are either black or white but not all white. A can see the hats of B and C; B can see the hats of A and C; C is blind. Each ...
1
vote
1answer
45 views

Proof of Soundness Lemma

We are given that $\Gamma \vdash \phi$ and want to show that for any truth assignment $\nu$ such that $\bar{\nu}(\psi) = T$ for all $\psi \in \Gamma$ then $\bar{\nu}(\phi)=T$ We are given the hint to ...
1
vote
1answer
19 views

Inference Lemma Proof?

Suppose that $\Gamma$ is a subset of $\mathcal{L_0}$, $\phi$ and $\psi$ formulas. If $\Gamma \vdash \psi$ and $\Gamma \vdash (\psi\to \phi)$ then $\Gamma \vdash \phi$. Proof: Let $\langle ...
0
votes
1answer
37 views

Properties that can be proven with induction on wff's?

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\to\}$ and $\textit{propositional symbols}=\{A_n\mid n\in\mathbb{N}\}$ for $n \in ...
1
vote
1answer
53 views

Translate the following sentence into conjunctive normal form

"Anyone who has cats as pets will not have mice": $$\forall x[\exists zHave(x,cat(z))]\rightarrow \forall y[\neg Have(x,mouse(y))]$$ I need to translate this into conjunctive normal form. So the ...
0
votes
1answer
58 views

Prove that John is not a light sleeper

Define each sentence in terms of CNF. Prove that John is not a light sleeper. ...