Sound and complete, Computer Engineering

Assignment Help:

Dictator Dim wants to replace counting, in particular, counting the population of his land. To keep an accurate population count, Dictator Dim has instructed his secretary to add one + symbol to a record each time a citizen is born, and one - symbol to the record whenever a citizen dies. This has been going on ever since his rule began.

Dictator Dim is not concerned so much with the actual total population of his lands, just with the net change in population since his rule began. He would be forever disgraced if the net population change were ever negative. Refusing to solve this problem by counting, Dictator Dim instructs his secretary to find a sound and complete logic for the subset of all records that would not disgrace him.
More formally, define the following truth concept WFF's = {+; -}, i.e., all strings composed of only plus and minus symbols.
A WFF x is true if every prefix of x contains at least as many + symbols as - symbols.

Find a logic for this truth concept by proving that it is sound and complete. Hint: it may help to define additional judgement form(s)


Related Discussions:- Sound and complete

Show types under which networks will be divided, What are the two broad typ...

What are the two broad types under which Networks will be divided? Ans: All computer networks fit in one of the two dimensions specifically: a)  Transmission Technology, thi

Describe one graphics and image editing tool, Question : Multimedia inv...

Question : Multimedia involves multiple modalities of text, audio, images, drawings, animation, and video (a) Describe three popular file formats for images (b) Most imag

Define elimination of common sub expression, Explain Elimination of common ...

Explain Elimination of common sub expression during code optimization An optimizing transformation is a regulation for rewriting a segment of a program to enhance its execution

Default communicator in mpi, Problem 1 (a) What is the difference betw...

Problem 1 (a) What is the difference between an MPI blocking send function and an MPI non-blocking send function? (b) What is a communicator in MPI? (c) Name correctly

What is replacement algorithm, What is replacement algorithm? When the ...

What is replacement algorithm? When the cache is full and a memory word that is not in the cache is referenced, the cache control hardware must decide which block should be del

4 variable k-maps, 4-variable K-maps have 16 squares which arearranged in 4...

4-variable K-maps have 16 squares which arearranged in 4 columns and 4 rows.  Columns and rows are labeled with 2 variables. The rows are arranged so that C or D ch

Where protocol operates to monitor and control n/w devices, Protocol used t...

Protocol used to monitor and control network devices operates at? Protocol operates at application layer to monitor and control network devices operates.

Exit command, Your shell must accept the exit command. This command will ...

Your shell must accept the exit command. This command will be in the form: e x i t When you encounter this command, your shell should terminate. Please note that when you

Logical representations, Logical Representations: If all human beings ...

Logical Representations: If all human beings spoke the same language, there would be a much more less misunderstanding in the world. The problem regarding with software engine

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd