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
1answer
41 views

Logic : How to determine whether these propositions are contradictory ?

http://postimg.org/image/iips2lwdj/ The question asks to draw a truth table with the values of three propositions (linked), and following this, to "Show that the three propositions are ...
1
vote
1answer
48 views

Prove or disprove a sentence using HPC

according to HPC: Let S be a set of sentences and α that is not in S. Prove or disprove : If $S\cup\{\alpha\} \vdash \beta$ and $S\cup\{\neg \alpha\} \vdash \beta$ then $S\vdash \beta$. It ...
0
votes
4answers
76 views

Use tableau to convert formula to DNF/CNF form

Is there any method that can be used to convert any formula do a DNF/CNF form using only the truth table? For example if I have the following formula p → ¬(q∨r) How can I convert it into DNF? ...
3
votes
2answers
48 views

Write $(p↔q)$ in DNF

I have the following formula: $(p↔q)$ and I have to write in DNF (disjunctive normal form) This is where I got so far: $(p↔q) = ((p→q)∧(q→p)) = ((¬p∨q)∧(¬q∨p))$ but here I got stuck. How ...
1
vote
1answer
39 views

Every positive formula is satisifiable

We say that a propositional logical formula is positive if it does not include the negation connective ¬ anywhere in it (but it may still use ∧, ∨, ↔, →, and propositions). Show that all ...
1
vote
2answers
37 views

Proving that a set with a quaternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{N\}$ of one logical connective is inadequate where $N$ is a quaternary connective that is defined as follows: $N(w,x,y,z)=((x\land y)\land(w\lor z))$ ...
2
votes
1answer
33 views

Question regarding using the natural deduction system

I have the following: Premise: ((V → ¬W) ∧ (X → Y)) Premise: (¬W → Z) Premise: (V ∧ X) |- (Z ∧Y) The part I want to know is how do I go about separating ...
2
votes
1answer
73 views

Argue that if a sentence has a proof, then it is a tautology

This is a corollary of the soundness theorem, which states that for a set of formulas $\Phi$ (of propositional logic) and a formula $\alpha$ : $$\Phi\vdash\alpha\Longrightarrow\Phi\vDash\alpha$$ What ...
1
vote
1answer
34 views

Equivalence of two biconditionals of propositional metalogic

In application to propositional metalogic, I am told that the following two biconditionals are equivalent: (i) Γ is satisfiable iff every finite subset of Γ is satisfiable. (ii) Γ ⊨ α iff some ...
0
votes
1answer
96 views

Disjunctive normal form and shannon normal form

Consider the formula (( true | (a <-> b)) & ((c | b) ^ a ^ b)). transform the formula into disjunctive normal form for the variable ordering a ≤ b ≤ c ≤ d. Also transform to Shannon normal form ...
0
votes
0answers
22 views

Construction of atomically closed tableu from a closed tableu

Suppose we have a closed tableu with at least one branch $\theta$ that contains $X$ and $\neg X$ where X is non-atomic formula. My strategy could be that of exploring the cases of X being an ...
-1
votes
1answer
62 views

Complete operator base logic [closed]

Show that $F={0,\to}$ is a complete operator basis by giving equivalent formulas for negation,conjunction and disjunction over F.
3
votes
1answer
58 views

What is the set of propositional formulas?

What is the set of propositional formulas? I am not sure if I understand this
1
vote
4answers
69 views

Filling in a missing portion of a truth table

I have the following truth table: $$ \boxed{ \begin{array}{c|c|c|c} a & b & c & x \\ \hline F & F & F & F \\ F & F & T & F \\ F & T & F ...
1
vote
1answer
56 views

Prove that the intersection of definable sets is definable

Hello I have a question : $F$ is a family of definable sets. Prove that the intersection of all the sets in the family is definable. ($F$ could be infinite) Definition (Definable): a set $K$ of ...
1
vote
1answer
53 views

Find indefinable set that is included in definable set.

Find $K\subseteq \operatorname{Ass} $ and $ K'\subseteq K$ such that $K$ is definable but $K'$ is not. Definition (Definable): a set $K$ of assignments is definable if there is a set of formulas A ...
2
votes
1answer
95 views

I'm wodering if this statement is provable in logic $ \lnot \alpha \to \lnot \lnot \lnot \alpha ) $

I've encountered this statement in my final exam $$ \lnot \alpha \to \lnot \lnot \lnot \alpha ) $$ there was no open parenthesis and from what I know this is invalid (not a well-formed formula) so ...
11
votes
4answers
707 views

Why is a statement “vacuously true” if the hypothesis is false, or not satisfied?

Why isn't a conditional statement said to "not apply" instead of be "vacuously true" if the hypothesis is not satisfied? That would seem more appropriate.
2
votes
2answers
52 views

Propositional Calculus, Can someone answer the following?

Can somebody please solve the following equations: \begin{align} 1. \quad (A \rightarrow B)\land (A\rightarrow \neg B)=\lnot A \quad \quad \\ \end{align} What I have got for it so far is ...
2
votes
3answers
84 views

Solving this logical puzzle by resolution doesn't work for me

In this document there is a logical puzzle: If the unicorn is mythical, then it is immortal. If the unicorn is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a ...
3
votes
4answers
136 views

Proving $ \neg ( \neg \alpha \wedge \neg \neg \alpha )$

I'm training to prove this statement , but first I need to know if this statement can be proved in : 1 - both in classical and Intuitionistic logic ( in this case i need to provide demonstration in ...
2
votes
4answers
80 views

How to prove this tautology using equivalences?

I am trying to prove that the following is a tautology: $(A \implies (B \implies C)) \implies ((A \implies (C \implies D)) \implies (A \implies (B \implies D)))$ To make progress, I thought I'd ...
2
votes
1answer
79 views

Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$. For example: ...
6
votes
2answers
131 views

Propositional Logic: Proof involving only the symbols $\{\rightarrow,F \}$

I feel like I literally tried everything. I'm exhausted, and could really use some help. I was instructed to prove some logic proposition using only the symbols $\{\rightarrow,F \}$. Let me first ...
3
votes
1answer
86 views

Satisfiability proof of formulas with pure literals

Let $\varphi$ be any propositional formula in negation normal form (NNF). A literal $\ell$ is pure in a formula $\varphi$, if the complement of $\ell$, $\ell^c$, does not occur in $\varphi$, where ...
1
vote
1answer
62 views

How to evaluate the single turnstile symbol ($\vdash$) in propositional logic?

Wikipedia says, that: $x \vdash y$ means y is provable from x (in some specified formal system). But what do you actually check or calculate, when you have $(a \land \lnot b) \vdash a$? Has $(a ...
0
votes
1answer
49 views

Rewrite predicate formulas in propositional calculus

Suppose that the universe of discourse of the atomic formula P(x,y) is the set {0,1,2,3,4,5}. Write each of the following propositions using dis-junctions, conjunctions and only one negation: 1) ∃x ...
3
votes
1answer
47 views

Prove that ≿ is transitive iff ≻ and ∼ are transitive

Let ≿ be a complete preference relation (as in game theory). How to prove that ≿ is transitive if and only if ≻ and ∼ are both transitive? My reasoning is as follows. ...
0
votes
1answer
56 views

I am trying to use proof of sequence correctly to make valid

Here I am trying to use a proof sequence so that the argument is valid (hint: the last A’ has to be inferred). (A → C) ∧ (C → B') ∧ B → A' Here are my steps I tried but not sure if this is correct ...
0
votes
0answers
86 views

Trying to justify each step correctly in proof sequence

I am trying Justify each step in the proof sequence below for correctly with [A → (B ∨ C)] ∧ B' ∧ C' → A' So I justified my steps here but I am not sure at 1 to 3 if I did it correctly. A → (B ∨ ...
1
vote
1answer
44 views

Prove that a boolean function using only $\vee$ and $\wedge$ must attain the value $1$ at least once

Please give me feedback on this Prove that a boolean function constructed only by using $\vee$ and $\wedge$ (without using $\sim$ ) must attain the value $1$ at least once.
2
votes
1answer
65 views

Proving $(p\to q)\land(p\to r) \equiv p\to(q\land r)$ using logic laws — short cut or incorrect?

Working through this problem: Using logic laws, show that the following are logically equivalent: $$(p\to q)\land(p\to r)\qquad\text{and}\qquad p\to(q\land r).$$ The way I did the problem is ...
0
votes
1answer
48 views

Exam preparation: logic - problems on (maximally) consistent sets

I am preparing for an exam on aspects of Logic related to propositional and first order logic. One of my revision exam questions is . I have attempted this question but I am really struggling with ...
-1
votes
2answers
136 views

Simplifying on logic Operations

I need simplify the following proposition to 2 logic operations using the laws of the algebra of propositions. Write each step on a separate line with the algebra law you used as a justification. ...
1
vote
1answer
53 views

Can't get Logical Error

Firstly I 'll mention Absorption laws : $((\sim p) \vee q) \wedge (\sim q)=(\sim p)$ $((\sim p) \vee q) \wedge p=q$ Also, $p \Longrightarrow q = (\sim p) \vee q$ And, $p \Longleftrightarrow q = ...
1
vote
1answer
57 views

If there are Predicates before Predicate Calculus, why is it called such?

In my understanding, predicates are synonyms of relations: mappings of an ordered set (a,b) to the set of values "True" and "False" Well, propositional calculus comes before predicate calculus, and ...
0
votes
2answers
88 views

Why $ M\models \forall x ( \alpha \to \beta)$ Is False? [closed]

if M be a model and $\alpha$ and $ \beta$ be two formula the following is False: $ M \models \forall x ( \alpha \to \beta)$ if and only if $ M \models \forall x \alpha$ has conclusion $ M \models ...
0
votes
1answer
61 views

Proving these are logically equivalent?

How to prove that these are logically equivalent using laws? a. $p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)$ I used the Conditional law and DeMorgan's Law and eventually arrived at $-(p ∨ q) ∧ -(p ∨ q)$ but ...
0
votes
0answers
44 views

Proof by contradiction that $P \rightarrow Q$ is true

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. So let's say the statement can be expressed by $P \rightarrow Q$. To prove that this statement is true, we look at the assumption ...
0
votes
1answer
34 views

Logical Equivalence of Wffs in Sentence, Predicate Logic using Tables, Interpretations Resp.

just curious if there is a formal name for the results that: a) Two wffs in Sentence Logic are equivalent iff their truth tables are equal , as binary functions of {T,F} b) Two wffs A,B in ...
3
votes
3answers
92 views

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. Is this valid?

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. I would say that this is false since the weather isn't directly influencing John's health. Am I right or wrong? Should I use ...
2
votes
1answer
85 views

What is the _simplest_ way to solve problems of this kind?

Two doors with talking doorknockers - one always tells the truth and one always lies. One door leads to death other to escape. Only one question may be asked to either of the door knockers. What would ...
2
votes
3answers
86 views

What is the negation of the statement “Every odd nmber is divisible by 2”.

Intuitively,I think it is "no odd number is divisible by 2" or it could be "every odd number is not divisible by 2". Is this a trivial question or is there more to it? What is the correct answer? BTW ...
4
votes
9answers
220 views

Why is the negation of $A \Rightarrow B$ not $A \Rightarrow \lnot B$?

The book I am reading says that the negation of "$A$ implies $B$" is "$A$ does not necessarily imply $B$" and not "$A$ implies not $B$". I understand the distinction between the two cases but why is ...
0
votes
0answers
48 views

Non Satisfiability of disjuction

Problem: If S1,S2 are (possibly infinite) sets of propositional formulas where their union: S1VS2 is not satisfiable, prove that there exists an ψ such that S1|=ψ and S2|=¬ψ. Can we say that if ...
1
vote
1answer
68 views

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable.

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. Okay can prove this by contradiction. So we say that a tableau $\tau$ is $\textit{satisfiable}$ iff there exists an ...
1
vote
1answer
86 views

direct hint to showing a formula is valid?

we know A formula is logically valid (or simply valid) if it is true in every interpretation. These formulas play a role similar to tautologies in propositional logic. which one could direct me to ...
4
votes
1answer
60 views

Show $\models(\phi\rightarrow(\psi\rightarrow\theta))\rightarrow((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow\theta))$

Question: Show $\models(\phi\rightarrow(\psi\rightarrow\theta))\rightarrow((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow\theta))$ Answer: (1) Let, ...
0
votes
1answer
43 views

how we can prove that argument $P_1,P_2,…,P_n $?

I ran into a one claims on LOGIC. how can add more direction or hint to me? if we have an argument $P_1,P_2,...,P_n $ such that $ n>3$ ($p_i$ is premise) why $P_1,P_2,....,P_n,P_1$ is ...
1
vote
0answers
37 views

How we can prove that the logical result of a set is effectively enumerable? [duplicate]

How we can prove that the logical result of $\{(p_i \vee $~ $p_{i+1}$$) $$: i \in \mathbb{N} \}$ is effectively enumerable ? Update: as one user requests, I add my method. I use truth table for ...